# 并查集 --- ## 一、什么是并查集 并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。[^1] --- 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。  --- ## 二、并查集的朴素实现 其实现过程有 - 初始化 - 合并 - 查询 --- #### 1. 初始化 ```c++ int fa[MAXN]; inline void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; } ``` 假如有编号为1, 2, 3, ..., n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。 --- #### 2. 查询 ```c int find(int x) { if(fa[x] == x) return x; else return find(fa[x]); } ``` 我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。 --- #### 3. 合并 ```c inline void merge(int i, int j) { fa[find(i)] = find(j); } ``` 合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。 --- ## 三、压缩路径 为什么要压缩路径？ 朴素的并查集在合并时是一个元素合并到下一元素上，最终会导致形成一条比较长的链，  这样从最后面查找其父亲时，效率较低。 --- 怎么解决呢？ 既然我们只关心一个元素对应的**根节点**，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样：  --- 如何实现？ 只要我们在查询的过程中，**把沿途的每个节点的父节点都设为根节点**即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现： --- ### 合并（路径压缩） ```c int find(int x) { if(x == fa[x]) return x; else{ fa[x] = find(fa[x]); //父节点设为根节点 return fa[x]; //返回父节点 } } ``` --- 以上代码常常简写为一行： ```c int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); } ``` --- 注意赋值运算符=的优先级没有三元运算符$?:$高，这里要加括号。 路径压缩优化后，并查集的时间复杂度已经比较低了，绝大多数不相交集合的合并查询问题都能够解决。然而，对于某些时间卡得很紧的题目，我们还可以进一步优化。 --- ## 四、进一步优化（按秩合并） 有些人可能有一个误解，以为路径压缩优化后，并查集始终都是一个**菊花图**（只有两层的树的俗称）。但其实，由于路径压缩只在查询时进行，也只压缩一条路径，所以并查集最终的结构仍然可能是比较复杂的。例如，现在我们有一棵较复杂的树需要与一个单元素的集合合并：  --- 假如这时我们要merge(7,8)，如果我们可以选择的话，是把7的父节点设为8好，还是把8的父节点设为7好呢？ 当然是后者。因为如果把7的父节点设为8，会使树的**深度**（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把8的父节点设为7，则不会有这个问题，因为它没有影响到不相关的节点。  --- 这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。 我们用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的**子树**的深度）。一开始，把所有元素的rank（**秩**）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。 路径压缩和按秩合并如果一起使用，时间复杂度接近 ![[公式]](https://www.zhihu.com/equation?tex=O%28n%29) ，但是很可能会破坏rank的准确性。 --- ### 初始化（按秩合并） ```c inline void init(int n) { for (int i = 1; i <= n; ++i) { fa[i] = i; rank[i] = 1; } } ``` ### 合并（按秩合并） ```c inline void merge(int i, int j) { int x = find(i), y = find(j); //先找到两个根节点 if (rank[x] <= rank[y]) fa[x] = y; else fa[y] = x; if (rank[x] == rank[y] && x != y) rank[y]++; //如果深度相同且根节点不同，则新的根节点的深度+1 } ``` --- 为什么深度相同，新的根节点深度要+1？如下图，我们有两个深度均为2的树，现在要merge(2,5)：  这里把2的父节点设为5，或者把5的父节点设为2，其实没有太大区别。我们选择前者，于是变成这样：  显然树的深度增加了1。另一种合并方式同样会让树的深度+1。 --- ## 五、例题和练习题目 || |---| |[亲戚](http://39.99.183.126:8888/p/YBTJ1346)| 1. 浴谷P1525, P1551 2. 浴谷p1892：https://www.luogu.com.cn/problem/P1892 3. 浴谷P1525 --- ## 六、拓展 注意并查集与其他算法的结合，比如在树中的trajan算法求lca，再比如与散列化（哈希）算法的结合等等。 [^1]:百度百科：并查集，https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin