并查集学习
一、并查集
1、定义
并查集是用来维护结点是否属于同一个连通块的数据结构。具体的，并查集可以维护下面的事情：
- 给出 n n n 个结点，初始时他们都是孤立的，你可以维护一个数据结构，实现下面两个操作：
- 1.给出 x , y x,y x,y，合并 x x x 和 y y y 所在的联通块。若 x , y x,y x,y 在同一个联通块内，则什么也不做。
- 2.给出 x , y x,y x,y，查找 x , y x,y x,y 是否在同一个联通块内。
- 两种操作时间复杂度均为 O ( n log n ) 。 O(n log n)。 O(nlogn)。
因为一个元素只可能属于一个集合，所以我们可以为每一个集合选取一个代表元。于是查询两个元素是否属于同一个集合实际上就是询问两个元素所在集合的代表元是否相同。这个询问的时间复杂度可以利用数组标记优化为 O ( 1 ) O(1) O(1)。
但是合并两个集合时需要改变其中一个集合中所有元素的代表元，时间复杂度仍然非常高，如何优化呢？
注意到，合并操作的时间复杂度远高于查询操作的复杂度，这启发我们通过一定的方式，提高查询操作的复杂度，降低合并操作的复杂度。
我们并不需要 O ( 1 ) O(1) O(1) 知道每个元素所属集合的代表元，这启发我们用森林来维护代表元。用森林中的一棵树代表一个集合，树根为对应集合的代表元。
这样，对于每棵树上的元素，查询其代表元时，时间复杂度与树的高度成正比。
对两个集合进行合并操作时，只需将其中一个集合的代表元（树根）指向另一个集合（树）的代表元即可。时间复杂度也与树的高度成正比。
这就是并查集。
2、初始化
初始的时候， n n n 个结点都是孤立的，所以我们将他们分别单独建成一棵树，每棵树只有恰好一个结点。
对于根结点，我们令它的父亲为它自身，这样也方便我们检测是否已经走到根结点。
for(int i=1;i<=n;i++) fa[i] = i;
当有 6 个结点的时候，这样初始化就会形成下图的森林：
3、查找
这里就可以用实际问题来理解：几个家族举行宴会，但由于所有人都很傻健忘，只记得自己的父亲是谁了。除了乌鲁鲁·。
然后，只有最长者知道他是最大的人，简称祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。
在这样的思想下，并查集的查找算法诞生了：当我们要查询 x x x 和 y y y 是否连通的时候，我们只需要简单地判断 i i i 的根是否等于 j j j 的根，如果不相等，那么说明不处于同一个连通块，如果相等，则说明处于同一个连通块。
下面是板子：
int fa[1000005]; // 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
int find(int x) {
// 寻找 x 的祖先
if (fa[x] == x){ // 如果 x 是祖先则返回
return x;
}else{
return find(fa[x]); // 如果不是则 x 的爸爸问 x 的爷爷
}
}
显然这样最终会返回 x x x 的祖先，并且上述查询操作的代码的时间复杂度取决于每个集合对应的树的高度。
下面演示了
7
7
7 号节点不断向上寻找寻找祖先的过程：
4、合并
宴会上，一个家族的祖先突然对另一个家族说：我们两个家族交情这么好，不如合成一 我们之前说过，并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。
下面是板子：
void union(int x, int y) {
// x 与 y 所在家族合并
x = find(x);
y = find(y);
fa[x] = y; // 把 x 的祖先变成 y 的祖先的儿子
}
可以看出，合并操作的时间复杂度取决于查找操作的时间复杂度，也就是每个集合对应的树的高度。
下图演示了查询
7
,
24
7,24
7,24 两个结点是否在同一个集合，如果不在，就合并的过程。
5、时间复杂度优化
不幸的是，上面代码看似优秀，但实际上，在最坏情况下时间复杂度仍然很高——因为森林中树的深度可能比较大。如果我们不停地从一个深度比较大的点向上寻找代表元，时间复杂度就令人难以接受。
下面我们来讲讲上述操作的优化操作。
查找的优化——路径压缩
这样的确可以达成目的，但是显然效率实在太低。
为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。
甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ，这就是路径压缩。
下面是一种实现的板子：
int find(int x) {
if (x == fa[x]) return fa[x];// 如果 x 是祖先(根)则返回
return fa[x] = find(fa[x]); // 查找 x 的祖先直到找到代表,于是顺手路径压缩
}
合并的优化—启发式合并（按秩合并）
一个祖先突然抖了个机灵：你们家族人比较少，搬家到我们家族里比较方便，我们要是搬过去的话太费事了。
由于需要我们支持的只有集合的合并、查询操作，当我们需要将两个集合合二为一时，无论将哪一个集合连接到另一个集合的下面，都能得到正确的结果。但不同的连接方法存在时间复杂度的差异。具体来说，如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于另一种连接方案，接下来执行查找操作的用时更小（也会带来更优的最坏时间复杂度）。
当然，我们不总能遇到恰好如上所述的集合——点数与深度都更小。鉴于点数与深度这两个特征都很容易维护，我们常常从中择一，作为估价函数。而无论选择哪一个，时间复杂度都为
O
(
m
α
(
m
,
n
)
)
O(m lpha(m,n))
O(mα(m,n))，我不会具体证明。
下面是板子：
for(int i = 1; i <= n; i++) {
fa[i] = i;
siz[i] = 1; // 集合大小初始化为 1
}
void union(int x, int y) {
x = find(x), y = find(y);
if (x == y) return; // 在同一集合，无需合并
if (siz[x] > siz[y]) // 保证小的合到大的里
swap(x, y);
fa[x] = y;
siz[y] += siz[x]; // 更新集合中元素个数
}
Ackermann函数与反Ackermann函数
同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为 O ( α ( n ) ) O(lpha(n)) O(α(n))，其中 α lpha α 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。
Ackermann 函数 A ( m , n ) A(m,n) A(m,n) 的定义是这样的：
A ( m , n ) = { n + 1 if m = 0 A ( m − 1 , 1 ) if m > 0 and n = 0 A ( m − 1 , A ( m , n − 1 ) ) otherwise A(m,n)= egin{cases} n + 1 & ext{if } m = 0 A(m - 1, 1) & ext{if } m > 0 ext{ and } n = 0 A(m - 1, A(m, n - 1)) & ext{otherwise} end{cases} A(m,n)=⎩ ⎨ ⎧n+1A(m−1,1)A(m−1,A(m,n−1))if m=0if m>0 and n=0otherwise
而反 Ackermann 函数 α ( n ) lpha(n) α(n) 的定义是阿克曼函数的反函数，即为最大的整数 m m m 使得 A ( m , m ) ≤ n A(m, m) le n A(m,m)≤n。
