Union-Find并查集模板

数组版本

class UnionFind {
    public int count; //连通分量个数
    public int[] parent; //储存每个节点的父节点
    public int[] size; //记录每棵树的重量(节点个数)

    //初始化构造方法
    public UnionFind(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    /* 将p和q连接 */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return; //已连通

        //小树接到大树下面，更为平衡
        if (size[rootP] > size[rootQ]) {
            size[rootP] += size[rootQ];
            parent[rootQ] = rootP;
        } else {
            size[rootQ] += rootP;
            parent[rootP] = rootQ;
        }
        count--;
    }

    /* 判断p和q是否连通 */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /* 找到x的根节点 */
    private int find(int x) {
        while (parent[x] != x) {
            //路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

HashMap版本

class UnionFind {
    public int count; //连通分量个数
    public HashMap<Integer, Integer> parent; //储存每个节点的父节点
    public HashMap<Integer, Integer> size; //记录每棵树的重量(节点个数)

    //初始化构造方法
    public UnionFind(int n) {
        this.count = n;
        this.parent = new HashMap<>();
        this.size = new HashMap<>();
        for (int i = 0; i < n; i++) {
            parent.put(i, i);
            size.put(i, 1);
        }
    }

    /* 将p和q连接 */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return; //已连通

        //小树接到大树下面，更为平衡
        if (size.get(rootP) > size.get(rootQ)) {
            size.put(rootP, size.get(rootP) + size.get(rootQ));
            parent.put(rootQ, rootP);
        } else {
            size.put(rootQ, size.get(rootP) + size.get(rootQ));
            parent.put(rootP, rootQ);
        }
        count--;
    }

    /* 判断p和q是否连通 */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /* 找到x的根节点 */
    private int find(int x) {
        while (parent.get(x) != x) {
            //路径压缩
            parent.put(x, parent.get(parent.get(x)));
            x = parent.get(x);
        }
        return x;
    }
}

hhhhh