并查集笔记

1 引例

某个城市里住 n 个人，现在给定关于 n 个人的 m 条信息（某两个人认识）。
假设所有认识的人属于同一单位，问最多有多少个单位？

2 定义

并查集：不相交集合。（树形结构）
把编号为 $i$ 的 N 个对象划为不相交集合。在每个集合中，选择其中某个元素代表所在集合。
操作：

1. 并：合并两个集合；
2. 查：查找某一元素属于哪个集合。

3 实现方法：

用编号最小的元素标记所在集合。
定义一个数组，下标表示编号，值为所在集合号。
方法：用每个集合编号最小的元素的编号表示集合号。这样每个集合里编号最小的元素的就是集合号等于编号的元素。

3.1 传统方法

1.查

 find(x)
{
    return x;
}

复杂度$O(1)$。
2.并
设两个集合号为 m,n (m < n) ,遍历整个数组，发现集合号是 n ,则改为m。
复杂度$O(n)$。
缺点：数量比较大时，可能合并的数组很小，但是要遍历整个数组。

3.2 有根树

添加了层次，父子关系。
比如7和8都是集合4的，而集合4和集合5都是集合2的。那么7和8就是集合2的。
1.查
逐次查找父集合，直到查到的父集合“值 = 集合号”为止。
复杂度$O(log\ n)$。
2. 并

merge(a,b)
{
    set[a]=b;
}

复杂度 $O(1)$。


此方法查找的最坏情况是$O(n)$。
为了避免这种情况，要将深度小的树合并到深度大的树去。

4.应用

4.1 最小生成树

每个边都有一个权值。
使用 Kruskal算法依靠并查集实现。
至少存在一棵最小生成树，它包含权值最小的边。
把边全部都进来，权值排序，选择权值最小的边，去掉多余的边，直到所有边处理完毕。
权重最小的边把两个连通，就相当于节点少了一个。然后转换为少一个节点的问题，从剩下的几个边里面选权重最小的，重复这个过程，直到节点数减为1。
相当于贪心算法。