概念
其实并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。
用途
- 维护无向图的连通性。支持判断两个点是否在同一连通块内。
- 判断增加一条边是否会产生环：用在求解最小生成树的Kruskal算法里。
操作
并查集主要就三个操作：初始化、合并、查找
初始化
一般来说，并查集的初始化用数组即可，例如数组Tree[i]，i表示某节点，tree[i]表示当前节点的根节点
查找函数
这里的查找和java集合类List中的查找函数get()并不一样，他的作用是查找该节点的根节点，如果集合的parent等于集合的编号（即还没有被合并或者没有同类），那么自然返回自身编号。如果不同那么就可以调用递归函数。
代码如下
// 并查集查找根节点
static int findRoot(int x, int[] arr) {
// 如果集合i的父亲是自己，说明自己就是源头，返回自己的标号
if (arr[x] == -1)
return x;
else // 否则查找集合i的父亲的源头
return findRoot(arr[x], arr);
}
若需要在查找过程中添加路径压缩的优化，我们修改上面这个函数为：
// 并查集查找根节点（优化算法,本质是将路径压缩了）
static int findRootUseful(int x, int[] arr) {
int res = 0;
if (arr[x] == -1)
return x;
else {
res = findRoot(arr[x], arr);
arr[x] = res; // 将当前结点的双亲结点设置为查找返回的根结点编号
return res;
}
}
合并
上面的图片就是关于合并的解法，至于怎么合并就是要看题目的要求了，详见代码示例中的注释
//set1表示x所在的集合，set2表示y所在的集合
// 合并两个集合,至于按照什么原则合并就要按照题目意思了，在这里我定义了两个变量，用以比较set1和set2的某种属性之间的差异
//如果rankX>rankY,就需要把y的集合合并到x的根节点下，也就是set2[y]=x，否则就是将x的集合放到y的根节点下，即set1[x]=y
static int rankX = 0;
static int rankY = 1;
static void union(int x, int y, int[] set1, int[] set2) {
x = findRootUseful(x, set1);
y = findRootUseful(y, set2);
if (x == y)
return;
else if (rankX > rankY) {
set2[y] = x;
} else {
if (rankX == rankY)
rankY++;
set1[x] = y;
}
}
