并查集
目录
并查集三步走 ¶
并查集，开始的时候大家都是孤岛，根节点就是自己，然后我们不断地合并、修改指针，直到所有边都访问到。
- 数组初始化，每个节点的
parent指针都指向自己。数组roots存放所有节点的祖先节点（根节点，路径压缩）【如果要求子集中元素数量，那么还要再创建一个counts数组，存储一份子集元素中的数量，需要在union中更新】。 - 根据所有相连的边，不断地进行查找、合并。
- 查找用递归、同时能修改查找路径上的所有节点的
parent指针，合并前先调用查找然后看是否同一子图，是则合并失败，不是则直接将parent指针修改一下即可。
**有向图是否有环？**拓扑排序 DAG ！
**无向图是否有环？**并查集！
关于求子集的个数、子集中元素的个数，可以试试把问题转化为图的问题，那么就可以转化为子图的数目、子图中元素数目，应用图的搜索、并查集等！
Java 代码 ¶
public class UFC {
private int[] roots;
public UFC(int n) {
// 并查集用数组存parent
roots = new int[n];
// 开始时都是孤岛，根节点的parent都指向自己
for (int i = 0; i < n; i++) {
roots[i] = i;
}
}
// find 查找是递归
public int findRoot(int i) {
// 根节点一定指向自己
if (roots[i] == i) return i;
roots[i] = findRoot(roots[i]);
return roots[i];
}
// union 合并改指针
public boolean union(int i, int j) {
int rootI = findRoot(i);
int rootJ = findRoot(j);
if (rootI == rootJ) return false;
// 把根节点的parent指针直接更改
roots[rootI] = rootJ;
return true;
}
}