目录

🧐一.并查集的基本概念&实例：

🤪二.并查集代码：

😂三：并查集的一些习题：

A.省份数量

B.等式方程的可满足性

---

🧐一.并查集的基本概念&实例：

并查集概念：将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

 有了上面的一定了解，我们再来看一个实例：

比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校， 起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下 数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。(负号下文解释)

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是： 西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个 人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子：

现在0集合有7个人，2集合有3个人，总共两个朋友圈,负数的个数就是集合的个数

注意事项：

我们一般将数组中的元素初始化为-1

(数组的下标:)             数组的下标对应集合中元素的编号

（数组的值array[i]:） 数组中如果为负数，负号代表根，数字代表该集合中元素个数

（数组的值array[i]:）数组中如果为非负数，代表该元素双亲在数组中的下标

并查集能干的事：

查找元素属于哪个集合 沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)

查看两个元素是否属于同一个集合 沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在

将两个集合归并成一个集合 将两个集合中的元素合并 将一个集合名称改成另一个集合的名称

🤪二.并查集代码：

import java.util.*;public class UnionFindSet { public int[] elem; public UnionFindSet(int n){ this.elem = new int[n]; Arrays.fill(elem,-1); } //查询x的根节点，返回根节点的下标 public int findRoot(int x){ if(x < 0){ throw new IndexOutOfBoundsException("下标不合法，是负数"); } //一直等到数组里面的值为负数时，才找到一个根 while(elem[x] >= 0){ x = elem[x]; } return x; } //查询x1和x2是否是同一个集合 public boolean isSameUnionFindSet(int x1,int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if(index1 == index2) return true; return false; } //这是合并操作 public void union(int x1,int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if(index1 == index2){ return ; } elem[index1] = elem[index1] + elem[index2]; elem[index2] = index1; } //查询集合的个数 public int getCount(){ int count = 0; for(int x : elem){ if(x < 0) count++; } return count; }}

那我们趁热打铁，来做两道题练习一下： 

😂三：并查集的一些习题：

A.省份数量

题目链接：. - 力扣（LeetCode）

思路：我们初始化一个一维数组表示并查集（数组大小为城市的个数），遍历这个二维数组（isConnected[i][j] 表示 i , j 两个城市相连），用并查集将相连接的城市合并到一个集合中，最后统计集合中元素的个数，就是要求的省份个数

class Solution { //A.省份数量 public int findCircleNum(int[][] isConnected) { int n = isConnected.length; UnionFindSet ufs = new UnionFindSet(n); //将连接在一起的城市合并 for(int i = 0;i < isConnected.length;i++){ for(int j = 0;j < isConnected[0].length;j++){ if(isConnected[i][j] == 1){ ufs.union(i,j); } } } //查找连接在一起的城市，即省份的个数，直接返回 return ufs.getCount(); }}/* 并查集的实现*/class UnionFindSet { public int[] elem; public UnionFindSet(int n){ this.elem = new int[n]; Arrays.fill(elem,-1); } //查询x的根节点，返回根节点的下标 public int findRoot(int x){ if(x < 0){ throw new IndexOutOfBoundsException("下标不合法，是负数"); } while(elem[x] >= 0){ x = elem[x]; } return x; } //查询x1和x2是否是同一个集合 public boolean isSameUnionFindSet(int x1,int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if(index1 == index2) return true; return false; } //这是合并操作 public void union(int x1,int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if(index1 == index2){ return ; } elem[index1] = elem[index1] + elem[index2]; elem[index2] = index1; } //查询集合的个数 public int getCount(){ int count = 0; for(int x : elem){ if(x < 0) count++; } return count; }}

运行结果：

B.等式方程的可满足性

题目链接：. - 力扣（LeetCode）

思路：我们将具有相同属性的元素放入一个集合中，接着再遍历一遍字符串数组，如果字符串中对应的元素是！说明不是一个集合，再从上述并查集中查找， 如果是一个集合的(矛盾了)，返回false;遍历完成后也没有出现上述情况，说明都是一个集合里，返回true，那么这个等式方程组就满足条件

class Solution { //B.等式方程的可满足性 public boolean equationsPossible(String[] equations) { UnionFindSet ufs = new UnionFindSet(26); //将具有相同属性的元素放入一个集合中 for(int i = 0;i < equations.length;i++){ if(equations[i].charAt(1) == '='){ ufs.union(equations[i].charAt(0) - 'a',equations[i].charAt(3) - 'a'); } } //如果字符串中对应的元素是！，说明不是一个集合，再从上述并查集中查找， (矛盾了)如果是一个集合的，返回false; for(int i = 0;i < equations.length;i++){ if(equations[i].charAt(1) == '!'){ //查找根节点的下标位置 int index1 = ufs.findRoot(equations[i].charAt(0) - 'a'); int index2 = ufs.findRoot(equations[i].charAt(3) - 'a'); if(index1 == index2) return false; } } return true; }}/* 并查集的实现 */class UnionFindSet { public int[] elem; public UnionFindSet(int n){ this.elem = new int[n]; Arrays.fill(elem,-1); } //查询x的根节点，返回根节点的下标 public int findRoot(int x){ if(x < 0){ throw new IndexOutOfBoundsException("下标不合法，是负数"); } while(elem[x] >= 0){ x = elem[x]; } return x; } //查询x1和x2是否是同一个集合 public boolean isSameUnionFindSet(int x1,int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if(index1 == index2) return true; return false; } //这是合并操作 public void union(int x1,int x2){ int index1 = findRoot(x1); int index2 = findRoot(x2); if(index1 == index2){ return ; } elem[index1] = elem[index1] + elem[index2]; elem[index2] = index1; } //查询集合的个数 public int getCount(){ int count = 0; for(int x : elem){ if(x < 0) count++; } return count; }}

运行结果：

 结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注，你们的鼓励是我创作的最大动力！