并查集(不相交集)详解

亦凉 2024-03-25 09:43 33阅读 0赞

**目录**

一.并查集

1.什么是并查集

2.并查集的基本操作

3.并查集的应用

4.力扣上的题目

二.三大操作

1.初始化

2.查找

3.合并

三.省份数量

1.题目描述

2.问题分析

3.代码实现

四.冗余连接

1.题目描述

2.问题分析

3.代码实现

--------------------

## 一.并查集 ##

### 1.什么是并查集 ###

并查集（Disjoint-set Union 或 Union-find）是一种数据结构，用于维护一些不相交（disjoint）的集合，支持合并两个集合以及判断两个元素是否属于同一个集合。

并查集可以使用树来实现，每个集合可以看做是一棵树，代表元素是根节点。使用路径压缩可以减少查找操作的时间复杂度，使用按秩合并可以减少合并操作的时间复杂度，使得并查集的时间复杂度可以达到近乎常数级别，因此在一些算法中广泛应用，比如 Kruskal 算法和 Tarjan 算法。

### 2.并查集的基本操作 ###

1.  **初始化**：将每个元素初始化为单独的集合，每个集合的代表元素就是自己；
2.  **查找**：给定一个元素，找到它所属的集合的代表元素；
3.  **合并**：将两个集合合并成一个集合，即将其中一个集合的代表元素作为另一个集合的代表元素的子节点。

### 3.并查集的应用 ###

并查集是一种用于维护集合（组）的数据结构，它通常用于解决一些离线查询、动态连通性和图论等相关问题。

其中最常见的应用场景是解决**图论中的连通性问题**，例如判断图中两个节点是否连通、查找图的连通分量、判断图是否为一棵树等等。并查集可以快速地合并两个节点所在的集合，以及查询两个节点是否属于同一个集合，从而有效地判断图的连通性。

并查集还可以用于解决一些离线查询问题，例如静态连通性查询和最小生成树问题，以及一些动态连通性问题，例如支持动态加边和删边的连通性问题。

总之，如果需要维护集合（组）的连通性信息，就可以考虑使用并查集。

现在举一个现实中的问题,判断一个人是否属于一个家族,通常一个家族里面两个人可能不是彼此认识的,但是A和B是亲属关系,B和C是亲属关系,此时我们可以判断出A和C就是亲属关系

![1d7d559b0cd24a3bba407b5330ab3105.png][]

由于家族关系可能错综复杂,这个时候我们是否可以找一个代表,这个人来代表这个家族,比如选择A来代表家族A,D来代表家族B,那么只要你和A有关系,你就是属于A家族的,你和D有关系,你就是属于B家族的

并查集就是解决这样的问题的.

### 4.力扣上的题目 ###

以下是一些力扣（LeetCode）上关于并查集（Union Find）的题目：

1.  朋友圈（547） https://leetcode-cn.com/problems/friend-circles/
2.  冗余连接（684） https://leetcode-cn.com/problems/redundant-connection/
3.  冗余连接 II（685） https://leetcode-cn.com/problems/redundant-connection-ii/
4.  岛屿数量（200） https://leetcode-cn.com/problems/number-of-islands/
5.  连通网络的操作次数（1319） https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
6.  表示数值的字符串（剑指 Offer 20） https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
7.  最大连通面积（面试题 16.19） https://leetcode-cn.com/problems/pond-sizes-lcci/
8.  能否连接形成区域（面试题 16.19） https://leetcode-cn.com/problems/pond-sizes-lcci/
9.  合并账户（721） https://leetcode-cn.com/problems/accounts-merge/
10. 判断能否形成等差数列（1502） https://leetcode-cn.com/problems/can-make-arithmetic-progression-from-sequence/

以上是一些力扣上的并查集题目，建议在练习时，先自己尝试思考解法，如果卡在某个地方，可以查看题解或者向其他程序员求助。

## 二.三大操作 ##

### 1.初始化 ###

我们把数组初始化-1,具体的作用我们之后再来分析具体的用处,具体含义就是,这个负数的相反数为这棵树的高度-1

![7659a0318dd94dc9a7141d5926056f12.png][]

public void init(int[] parent) {
            //初始值设置为-1
            for (int i = 0; i < parent.length; ++i) {
                parent[i] = -1;
            }
    
        }

### 2.查找 ###

不进行路径压缩的查找简单粗暴的,它的目的就是为了**找到结点i的根结点**,直接看代码

public int find(int[] parent, int i) {
            if (parent[i] < 0) {//当前结点为根结点,终止
                return i;
            } else {
                return parent[i];     //返回父节点
            }
        }

这个时候我们来研究一下进行路径压缩的查找方式,我们需要合并0和4,如果我们只是粗暴的合并的话,这个时候0指向3,这个时候其实的查询长度就是越来越长,时间复杂度为O(n)

![cc1ef3b33e9a421d984fafe5ab5ab4e3.png][]

所以这个时候我们不进行路径压缩,压缩之后的图是这样的,这个时候时间复杂度大大降低,我们每次查找根结点的时候,只需要查找一次(递归一次)便可以找到根结点

进行路径压缩的查找方法要进行两个操作,最终目的肯定还是要找寻到根结点,但是其次他也进行了路径的压缩,例如下图一样,把本来的4指向3,修改成了4指向了2,其实可以精炼成一句话:找到根结点,并且把路径上所有节点的父亲结点修改为根结点.这样树的高度就变成了1(只含有一个结点(根结点)的高度为0).

![e4953dcb36884d6d922e38ad6a7b1960.png][]

public int find(int[] parent, int i) {
            if (parent[i] < 0) {//当前结点为根结点,终止
                return i;
            } else {
                parent[i] = find(parent, parent[i]);  //父节点设为根结点
                return parent[i];     //返回父节点
            }
    
    
        }

### 3.合并 ###

合并操作也可以简单粗暴的进行合成,我们只需要找到各自的祖先,任意的将一个合并到另一个上边即可,直接看代码

public void union(int[] parent, int i, int j) {
            int i_parent = find(parent, i);//寻找i的根结点
            int j_parent = find(parent, j);//寻找j的根结点
            parent[i_parent]=j_parent;//将根结点为i_parent的树合并到根结点j_parent上
        }

如果我们这个时候进行合并可能会出现这种情况,也就是一个高度较大的数合并到了一个高度较小的树上面,这个时候树的高度就会增加,如果我们是高度小的树合并到高度较大的树上边(两颗树的高度不相等),这个时候树的高度便不会增加,自然查找的时候会更加快速的查找到.

![327c998758d2421dafa446679d67d1c5.png][]

**进行按秩(树的高度)进行合并**

这种合并方式就是为了解决上面所提到的问题,合并是便会是这种情况,但是我们如果判断两棵树的高度大小呢,这个时候就可以解释以下初始化的为-1的目的了,一**:如果当前结点的值为负数,可以判断当前结点为根结点**,二.**当前结点越小(也就是相反数越大),说明当前树的高度越大**,我们只需要把更大的根结点的值合并到更小的根结点值上,便可以解决这个问题了.

![a18fb4e8b64141a89ea5264f14fc10b9.png][]

这个时候存在一个特殊情况,也就是两棵树的高度一样高.这个时候无论如何进行合并,树的高度度会增加,因此这个时候我们可以把一个根结点合并到另一个根结点上,并把合并到的根结点的值减一

![a155d634527d4e83bedce6021b09a31e.png][]

public void union(int[] parent, int i, int j) {
            int i_parent = find(parent, i);//寻找i的根结点
            int j_parent = find(parent, j);//寻找j的根结点
            if (i_parent != j_parent) {//此时的根结点相同,没有合并的必要
                if (parent[i_parent] < parent[j_parent]) {//此时表示i_parent的秩比j_parent的秩大
                    parent[j_parent] = i_parent;//把j_parent合并到i_parent上
                } else {
                    if (parent[i_parent] == parent[j_parent]) {
                        parent[j_parent]--;
                    }
                    parent[i_parent] = j_parent;//把i_parent合并到j_parent上
    
                }
    
            }
        }

## 三.省份数量 ##

### 1.题目描述 ###

> 有 `n` 个城市，其中一些彼此相连，另一些没有相连。如果城市 `a` 与城市 `b` 直接相连，且城市 `b` 与城市 `c` 直接相连，那么城市 `a` 与城市 `c` 间接相连。
> 
> **省份** 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
> 
> 给你一个 `n x n` 的矩阵 `isConnected` ，其中 `isConnected[i][j] = 1` 表示第 `i` 个城市和第 `j` 个城市直接相连，而 `isConnected[i][j] = 0` 表示二者不直接相连。
> 
> 返回矩阵中 **省份** 的数量。

力扣:[力扣][Link 1]

### 2.问题分析 ###

这是一道很典型的并查集问题,题目的意思就是城市之间相连就是一个省份,把相连的城市合并为一颗树,最终就是寻找有多少个根结点(有多少颗树),也就是parent\[i\]有多少个是小于0的值,就是一棵树,最终返回数量就可以了

### 3.代码实现 ###

public void init(int[] parent) {
            //初始值设置为-1
            for (int i = 0; i < parent.length; ++i) {
                parent[i] = -1;
            }
    
        }
    
        public int find(int[] parent, int i) {
            if (parent[i]<0) {
                return i;
            } else {
                parent[i] = find(parent, parent[i]);  //父节点设为根结点
                return parent[i];     //返回父节点
            }
    
    
        }
    
        public void union(int[] parent, int i, int j) {
            int i_parent = find(parent, i);//寻找i的祖先
            int j_parent = find(parent, j);//寻找j的祖先
            if (i_parent != j_parent) {//此时的祖先相同,没有合并的必要
                if (parent[i_parent] < parent[j_parent]) {//此时表示i_parent的秩比j_parent的秩大
                    parent[j_parent] = i_parent;//把j_parent合并到i_parent上
                } else {
                    if (parent[i_parent] == parent[j_parent]) {
                        parent[j_parent]--;
                    }
                    parent[i_parent] = j_parent;//把i_parent合并到j_parent上
    
                }
    
            }
        }
        public int findCircleNum(int[][] isConnected) {
            int[] parent = new int[isConnected.length];
            init(parent);
            for (int i = 0; i < isConnected.length; ++i) {
                for (int j = i + 1; j < isConnected[0].length; ++j) {
                    if (isConnected[i][j] == 1) {
                        union(parent, i, j);
                    }
                }
            }
            int cnt = 0;
            for (int i = 0; i < parent.length; ++i) {
                if (parent[i] < 0)
                    cnt++;
    
            }
            return cnt;
        
    
        }

## 四.冗余连接 ##

### 1.题目描述 ###

> 树可以看成是一个连通且 **无环** 的 **无向** 图。
> 
> 给定往一棵 `n` 个节点 (节点值 `1～n`) 的树中添加一条边后的图。添加的边的两个顶点包含在 `1` 到 `n` 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 `n` 的二维数组 `edges` ，`edges[i] = [ai, bi]` 表示图中在 `ai` 和 `bi` 之间存在一条边。
> 
> 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 `n` 个节点的树。如果有多个答案，则返回数组 `edges` 中最后出现的边。

力扣:[力扣][Link 2]

### 2.问题分析 ###

题目的意思就是不能出现环,也就是如果两个两个点已经连通了,这个时候不能再在这两个点添加一条边,这个时候就冗余了,我们都知道一个连通分量有n个顶点,n-1条边,而这道题一共有n条边,我们需要寻找的就是这一条冗余的边,当find(parent,i,j)的根结点一样的时候,这个时候这两个顶点之间的边一定是冗余的,找到这样的一条边即可.

### 3.代码实现 ###

public void init(int[] parent) {
            for (int i = 0; i < parent.length; ++i) {
                parent[i] = -1;
            }
        }
    
        public int find(int[] parent, int i) {
            if (parent[i] < 0)
                return i;
            else {
                parent[i] = find(parent, parent[i]);
                return parent[i];
            }
        }
    
        public void union(int[] parent, int i, int j) {
            int i_parent = find(parent, i);
            int j_parent = find(parent, j);
            if (i_parent != j_parent) {
                if (parent[i_parent] < parent[j_parent]) {
                    parent[j_parent] = i_parent;
                } else {
                    if (parent[i_parent] == parent[j_parent]) {
                        parent[j_parent]--;
                    }
                    parent[i_parent] = j_parent;
                }
            }
        }
    
        public int[] findRedundantConnection(int[][] edges) {
            int[] parent = new int[edges.length+1];
            init(parent);
            for (int i = 0; i < edges.length; ++i) {
                if (find(parent, edges[i][0]) != find(parent, edges[i][1])) {
                    union(parent, edges[i][0], edges[i][1]);
                } else {
                    return edges[i];
                }
            }
            return null;
    
    
        }

[1d7d559b0cd24a3bba407b5330ab3105.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/7bddb8a518774e94bbaed6dbf143588d.png
[7659a0318dd94dc9a7141d5926056f12.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3723c9aa99dc4c16a28a111b518edf52.png
[cc1ef3b33e9a421d984fafe5ab5ab4e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1c77e00f15b948709fc3abf555e029ce.png
[e4953dcb36884d6d922e38ad6a7b1960.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/60ef9f639b1e44b3bedc1981724f95d0.png
[327c998758d2421dafa446679d67d1c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/069bc97220124c9eab7ee9410a9236c5.png
[a18fb4e8b64141a89ea5264f14fc10b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/095011a506924bdfaf55223611ea57e9.png
[a155d634527d4e83bedce6021b09a31e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9ee09109c48a4d09b8da83836a475bd3.png
[Link 1]: https://leetcode.cn/problems/number-of-provinces/description/
[Link 2]: https://leetcode.cn/problems/redundant-connection/description/