并查集

• 并查集可以解决什么问题：连通性问题。
  • 可以将两个元素添加到同一个集合中。
  • 可以判断两个元素在不在同一个集合中。

并查集理论基础

• 并查集可以解决什么问题：连通性问题。
  • 可以将两个元素添加到同一个集合中。
  • 可以判断两个元素在不在同一个集合中。
• 我们将三个元素 A，B，C （分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通呢？
  • 只需要用一个一维数组来表示，即：root[A] = B，root[B] = C 这样就表述 A 与 B 与 C连通了。
  • 这里要讲到寻根思路，只要 A ，B，C 在同一个根下就是同一个集合。
    • 给出A元素，就可以通过 root[A] = B，root[B] = C，找到根为 C。
    • 给出B元素，就可以通过 root[B] = C，找到根也为为 C，说明 A 和 B 是在同一个集合里。
    • 如何表示 C 也在同一个集合里呢？ 我们需要 root[C] = C，即C的根也为C，这样就方便表示 A，B，C 都在同一个集合里了。

并查集模板代码

• 基于上述例子，我们不难写出并查集的下述模板代码：

  • 初始化并查集数组：

    public int[] init(int n) {
        int[] root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        return root;
    }

  • 找到当前元素的根结点（同时还压缩了路径）：

    public int find(int[] root, int x) {
        if (root[x] == x) { // 说明当前元素的根就是它自己
            return x;
        }
        // 让当前元素 x 的父节点直接变为集合的根结点，即压缩了路径
        return root[x] = find(root, root[x]);
    }

  • 判断两个元素是否在一个集合中：

    public boolean isSameCollection(int[] root, int x, int y) {
        int xRoot = find(root, x);
        int yRoot = find(root, y);
        if (xRoot == yRoot) {
            return true;
        }
        return false;
    }

  • 将两个元素所属的不同集合合并为一个集合：

    public void join(int[] root, int x, int y) {
        int xRoot = find(root, x);
        int yRoot = find(root, y);
        if (xRoot == yRoot) {
            return;
        }
        // 让第二个根结点的父节点变为第一个根结点，实现集合的合并
        root[yRoot] = xRoot;
    }