15、并查集

1、QuickFind

public interface UF {

    int getSize();

    /**
     * 查看元素 p 和元素 q 是否所属一个集合
     */
    boolean isConnected(int p, int q);

    /**
     * 合并元素 p 和元素 q 所属的集合
     */
    void unionElements(int p, int q);

}

QuickFind
isConnected(p, q)：O(1)
unionElements(p, q)：O(n)

public class UnionFind1 implements UF {

    private final int[] id;

    public UnionFind1(int size) {
        id = new int[size];
        for (int i = 0; i < size; i++) id[i] = i;
    }

    @Override
    public int getSize() {
        return id.length;
    }

    /**
     * 查找元素 p 所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) throw new IllegalArgumentException("p is out of bound.");
        return id[p];
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pID = find(p);
        int qID = find(q);

        if (pID == qID) return;

        for (int i = 0; i < id.length; i++) {
            if (id[i] == pID) id[i] = qID;
        }
    }
}

2、QuickUnion

QuickUnion
isConnected(p, q)：O(h)
unionElements(p, q)：O(h)
h 为树的高度，极端情况下，并查集中的树可能会退化成一个链表

public class UnionFind2 implements UF {

    private final int[] parent;

    public UnionFind2(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) parent[i] = i;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素 p 所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) p = parent[p];
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        parent[pRoot] = qRoot;
    }
}

3、基于 size 进行优化

sz[i] 代表以 i 为根的集合中的元素个数
让 "元素个数少的集合" 合并到 "元素个数多的集合" 上，使得合并后的新树，深度尽量不要增加

public class UnionFind3 implements UF {

    private final int[] parent;
    private final int[] sz; // sz[i] 代表以 i 为根的集合中的元素个数

    public UnionFind3(int size) {
        parent = new int[size];
        sz = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素 p 所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) p = parent[p];
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 让 "元素个数少的集合" 合并到 "元素个数多的集合" 上: 合并后的新树, 深度尽量不要增加
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        } else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }
}

4、基于 rank 进行优化

rank[i] 代表以 i 为根的集合所表示的树的层数
让 "层数低的集合" 合并到 "层数高的集合" 上，使得合并后的新树，深度尽量不要增加

public class UnionFind4 implements UF {

    private final int[] parent;
    private final int[] rank; // rank[i] 代表以 i 为根的集合所表示的树的层数

    public UnionFind4(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素 p 所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) p = parent[p];
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 让 "层数低的集合" 合并到 "层数高的集合" 上: 合并后的新树, 深度尽量不要增加
        if (rank[pRoot] < rank[qRoot]) parent[pRoot] = qRoot;
        else if (rank[qRoot] < rank[pRoot]) parent[qRoot] = pRoot;
        else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
}

5、路径压缩 1

基于 rank 的优化 + 路径压缩 1
rank[i] 代表以 i 为根的集合所表示的树的层数的排名
让 "层数排名低的集合" 合并到 "层数排名高的集合" 上，使得合并后的新树，深度尽量不要增加
平均来看，近乎是 O(1) 级别的

public class UnionFind5 implements UF {

    private final int[] parent;
    private final int[] rank; // rank[i] 代表以 i 为根的集合所表示的树的层数的排名

    public UnionFind5(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素 p 所对应的集合编号, 同时压缩树的高度使其尽可能的矮(路径压缩)
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) {
            parent[p] = parent[parent[p]]; // 路径压缩, p 指向 p 的爷爷, 不用维护 rank
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 让 "层数排名低的集合" 合并到 "层数排名高的集合" 上: 合并后的新树, 深度尽量不要增加
        if (rank[pRoot] < rank[qRoot]) parent[pRoot] = qRoot;
        else if (rank[qRoot] < rank[pRoot]) parent[qRoot] = pRoot;
        else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
}

5、路径压缩 2

基于 rank 的优化 + 路径压缩 2
rank[i] 代表以 i 为根的集合所表示的树的层数的排名
让 "层数排名低的集合" 合并到 "层数排名高的集合" 上，使得合并后的新树，深度尽量不要增加
平均来看，近乎是 O(1) 级别的

public class UnionFind6 implements UF {

    private final int[] parent;
    private final int[] rank; // rank[i] 代表以 i 为根的集合所表示的树的层数的排名

    public UnionFind6(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找元素 p 所对应的集合编号, 同时压缩树的高度使其尽可能的矮(路径压缩)
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) throw new IllegalArgumentException("p is out of bound.");

        if (p == parent[p]) return p;

        parent[p] = find(parent[p]);
        return parent[p];
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot) return;

        // 让 "层数排名低的集合" 合并到 "层数排名高的集合" 上: 合并后的新树, 深度尽量不要增加
        if (rank[pRoot] < rank[qRoot]) parent[pRoot] = qRoot;
        else if (rank[qRoot] < rank[pRoot]) parent[qRoot] = pRoot;
        else {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
}

本栏目推荐文章
• 学习 Rust 的 15 种方法
• OpenCV计算机视觉学习（15）——浅谈图像处理的饱和运算和取模运算
• abc097d<并查集，排列>
• Docker：docker部署mqtt(eclipse-mosquitto:2.0.15)服务
• leetcode 15.三数之和
• QT开发 QT5.15.2安装(换源极速安装)
• 15-Prometheu：Kubernete 怎样实现自动化服务监控告警？
• 并查集数组模板
• 代码随想录 day15 十二题二叉树
• 力扣15-三数之和