并查集(不相交集)详解

目录

一.并查集

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就是亲属关系

 由于家族关系可能错综复杂,这个时候我们是否可以找一个代表,这个人来代表这个家族,比如选择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

    public void init(int[] parent) {//初始值设置为-1for (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)

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

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

    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上}

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

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

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

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

    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 表示二者不直接相连。

返回矩阵中 省份 的数量。

力扣:力扣

2.问题分析

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

3.代码实现

    public void init(int[] parent) {//初始值设置为-1for (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 中最后出现的边。

力扣:力扣

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;}