算法笔记【2】并查集

一时失言乱红尘 2023-01-09 12:58 150阅读 0赞

# 算法笔记【2】 并查集 #

## 并查集简介 ##

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些**元素分组**的问题。它管理一系列**不相交的集合**，并支持两种操作：

*  **合并**（Union）：把两个不相交的集合合并为一个集合。
 *  **查询**（Find）：查询两个元素是否在同一个集合中。

当然，这样的定义未免太过学术化，看完后恐怕不太能理解它具体有什么用。所以我们先来看看并查集最直接的一个应用场景：**亲戚问题**。

> **题目背景**  
> 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。  
> **题目描述**  
> 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。  
> **输入格式**  
> 第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。  
> 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。  
> 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。  
> **输出格式**  
> P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

这其实是一个很有现实意义的问题。我们可以建立模型，把所有人划分到若干个不相交的集合中，每个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。因此，这里就可以考虑用并查集进行维护了。

## 并查集的引入 ##

并查集的重要思想在于，**用集合中的一个元素代表集合**。我曾看过一个有趣的比喻，把集合比喻成**帮派**，而代表元素则是**帮主**。接下来我们利用这个比喻，看看并查集是如何运作的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]

最开始，所有大侠各自为战。他们各自的帮主自然就是自己。*（对于只有一个元素的集合，代表元素自然是唯一的那个元素）*

现在1号和3号比武，假设1号赢了（这里具体谁赢暂时不重要），那么3号就认1号作帮主\*（合并1号和3号所在的集合，1号为代表元素）\*。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]

现在2号想和3号比武\*（合并3号和2号所在的集合）*，但3号表示，别跟我打，让我帮主来收拾你*（合并代表元素）\*。不妨设这次又是1号赢了，那么2号也认1号做帮主。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 2]

现在我们假设4、5、6号也进行了一番帮派合并，江湖局势变成下面这样：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 3]

现在假设2号想与6号比，跟刚刚说的一样，喊帮主1号和4号出来打一架（帮主真辛苦啊）。1号胜利后，4号认1号为帮主，当然他的手下也都是跟着投降了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 4]

好了，比喻结束了。如果你有一点图论基础，相信你已经觉察到，这是一个**树**状的结构，要寻找集合的代表元素，只需要一层一层往上访问**父节点**（图中箭头所指的圆），直达树的**根节点**（图中橙色的圆）即可。根节点的父节点是它自己。我们可以直接把它画成一棵树：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 5]

用这种方法，我们可以写出最简单版本的并查集代码。

### 初始化 ###

class DisjointSetUnion { 
        int[] f;
    
        public DisjointSetUnion(int n) { 
            this.f = new int[n];
            for (int i = 0; i < n; i++) { 
                this.f[i] = i;
            }
        }
    }

假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组f\[\]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

### 查询 ###

public int find(int x) { 
        return f[x] == x ? x : find(f[x]);
    }

我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

### 合并 ###

public void merge(int i, int j){ 
        fa[find(i)] = find(j);
    }

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。

## 路径压缩 ##

最简单的并查集效率是比较低的。例如，来看下面这个场景：

![在这里插入图片描述][20210121145723264.png_pic_center]

现在我们要merge(2,3)，于是从2找到1，fa\[1\]=3，于是变成了这样：

![在这里插入图片描述][20210121145730161.png_pic_center]

然后我们又找来一个元素4，并需要执行merge(2,4)：

![在这里插入图片描述][20210121145738739.png_pic_center]

从2找到1，再找到3，然后fa\[3\]=4，于是变成了这样：

![在这里插入图片描述][20210121145756224.png_pic_center]

大家应该有感觉了，这样可能会形成一条长长的**链**，随着链越来越长，我们想要从底部找到根节点会变得越来越难。

怎么解决呢？我们可以使用**路径压缩**的方法。既然我们只关心一个元素对应的**根节点**，那我们希望每个元素到根节点的路径尽可能短，最好只需要一步，像这样：

![在这里插入图片描述][20210121145805870.png_pic_center]

其实这说来也很好实现。只要我们在查询的过程中，**把沿途的每个节点的父节点都设为根节点**即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现：

public int find(int x) { 
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

注意赋值运算符=的优先级没有三元运算符?:高，这里要加括号。

路径压缩优化后，并查集的时间复杂度已经比较低了，绝大多数不相交集合的合并查询问题都能够解决。然而，对于某些时间卡得很紧的题目，我们还可以进一步优化。

## 按秩合并 ##

有些人可能有一个误解，以为路径压缩优化后，并查集始终都是一个**菊花图**（只有两层的树的俗称）。但其实，由于路径压缩只在查询时进行，也只压缩一条路径，所以并查集最终的结构仍然可能是比较复杂的。例如，现在我们有一棵较复杂的树需要与一个单元素的集合合并：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 6]

假如这时我们要merge(7,8)，如果我们可以选择的话，是把7的父节点设为8好，还是把8的父节点设为7好呢？

当然是后者。因为如果把7的父节点设为8，会使树的**深度**（树中最长链的长度）加深，原来的树中每个元素到根节点的距离都变长了，之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩，但路径压缩也是会消耗时间的。而把8的父节点设为7，则不会有这个问题，因为它没有影响到不相关的节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 7]

这启发我们：我们应该把简单的树往复杂的树上合并，而不是相反。因为这样合并后，到根节点距离变长的节点个数比较少。

我们用一个数组rank\[\]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的**子树**的深度）。一开始，把所有元素的rank（**秩**）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用，时间复杂度接近 \[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xJkeupH4-1611212170259)(https://www.zhihu.com/equation?tex=O%28n%29)\] ，但是很可能会破坏rank的准确性。

值得注意的是，按秩合并会带来额外的**空间复杂度**，可能被一些卡空间的毒瘤题卡掉。

### 初始化（按秩合并） ###

class DisjointSetUnion { 
        int[] f;
        int[] rank;
    
        public DisjointSetUnion(int n) { 
            	this.rank = new int[n];
                this.f = new int[n];
                for (int i = 0; i < n; i++) { 
                    this.f[i] = i;
                    this.rank[i] = 1;
                }
        }
    }

### 合并（按秩合并） ###

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)：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 8]

这里把2的父节点设为5，或者把5的父节点设为2，其实没有太大区别。我们选择前者，于是变成这样：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 9]

显然树的深度增加了1。另一种合并方式同样会让树的深度+1。

## 并查集的应用 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 10]

大家看出这道题和并查集的关系了吗？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 11]

> 这是二维版本，题目中的三维版本是类似的

大家看看上面这张图，是不是看出一些门道了？我们把所有空洞划分为若干个集合，一旦两个空洞相交或相切，就把它们放到同一个集合中。

我们还可以划出2个**特殊元素**，分别表示**底部**和**顶部**，如果一个空洞与底部接触，则把它与表示底部的元素放在同一个集合中，顶部同理。最后，只需要看**顶部和底部是不是在同一个集合中**即可。这完全可以通过并查集实现。来看代码：

public class Solution3958 { 
    
        public static void main(String[] args) { 
            // 高度
            int h = 10;
            // 半径
            int r = 3;
            // 圆点
            int[][] points = new int[][]{ { 1, 3, 2}, { 1, 3, 3}, { 2, 3, 4}, { 3, 4, 4}, { 3, 5, 12}};
            minCostConnectPoints(h, r, points);
    
        }
    
        public static void minCostConnectPoints(int h, int r, int[][] points) { 
            //圆的个数
            int n = points.length;
            DisjointSetUnion disjointSetUnion = new DisjointSetUnion(n + 2);
    
            for (int i = 0; i < n; i++) { 
                if (points[i][2] <= r) { 
                    // 与底部接触的圆点
                    disjointSetUnion.unionSet(i, n);
                }
                if (points[i][2] + r >= h) { 
                    // 与顶部接触
                    disjointSetUnion.unionSet(i, n + 1);
                }
            }
    
            // 找出所有相连的圆
            for (int i = 0; i < n; i++) { 
                for (int j = i + 1; j < n; j++) { 
    
                    if (nextTo(points[i][0], points[i][1], points[i][2], points[j][0], points[j][1], points[j][2], r)) { 
                        disjointSetUnion.unionSet(i, j);
                    }
    
                }
            }
    
            System.out.println(disjointSetUnion.find(n) == disjointSetUnion.find(n + 1) ? "Yes" : "No");
    
        }
    
        /** * 是否相交或者相切 */
        public static boolean nextTo(int x, int y, int z, int x1, int y1, int z1, int r) { 
            return (x - x1) * (x - x1) + (y - y1) * (y - y1) + (z - z1) * (z - z1) <= 4 * r * r;
        }
    
        static class DisjointSetUnion { 
            int[] f;
            int[] rank;
            int n;
    
            public DisjointSetUnion(int n) { 
                this.n = n;
                this.rank = new int[n];
                Arrays.fill(this.rank, 1);
                this.f = new int[n];
                for (int i = 0; i < n; i++) { 
                    this.f[i] = i;
                }
            }
    
            /** * 找到传入x节点的root节点 * * @param x 顶点 * @return root节点 */
            public int find(int x) { 
                return f[x] == x ? x : (f[x] = find(f[x]));
            }
    
            /** * 判断传入的顶点是否在图中形成回路 */
            public void unionSet(int x, int y) { 
                // 找到 x y 的根节点位置 fx fy
                int fx = find(x), fy = find(y);
    
                // 比较fx和fy两个根节点的深度 把小的父节点设置给大的一个
                if (rank[fx] <= rank[fy]) { 
                    f[fx] = fy;
                } else { 
                    f[fy] = fx;
                }
                // 应为两个树的深度相同，所以合并后父节点的树深度会增加1
                if (rank[fx] == rank[fy] && fx != fy) { 
                    rank[fy]++;
                }
            }
        }
    }

并查集的应用还有很多，例如最小生成树的[Kruskal][]算法等。这里就不细讲了。总而言之，凡是涉及到元素的分组管理问题，都可以考虑使用并查集进行维护。

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/08aecd7a79974d7cb282c516cfdd6b7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210121145640682.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210121145651149.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210121145658742.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210121145706728.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210121145713517.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[20210121145723264.png_pic_center]: https://img-blog.csdnimg.cn/20210121145723264.png#pic_center
[20210121145730161.png_pic_center]: https://img-blog.csdnimg.cn/20210121145730161.png#pic_center
[20210121145738739.png_pic_center]: https://img-blog.csdnimg.cn/20210121145738739.png#pic_center
[20210121145756224.png_pic_center]: https://img-blog.csdnimg.cn/20210121145756224.png#pic_center
[20210121145805870.png_pic_center]: https://img-blog.csdnimg.cn/20210121145805870.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210121145910944.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210121145917902.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20210121145929299.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20210121145936435.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210121150325241.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/2021012114595746.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[Kruskal]: https://blog.csdn.net/Zack_tzh/article/details/112903512
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200721144257696.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70