目录

并查集的实现

2022-04-19 约 524 字预计阅读 2 分钟

目录

回顾

之前在做剑指Offer专项版的时候，图的搜索那章，我总结了并查集的三步走：

并查集三步走

并查集，开始的时候大家都是孤岛，根节点就是自己，然后我们不断地合并、修改指针，直到所有边都访问到。

数组初始化，每个节点的 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;
  }
}