并查集模板

  

引言：

关于“并查集”的解释和使用场景网上有很多教程，这里就不在啰嗦了。仅提供代码模板方便知情人快速使用。

并查集的java实现

// 开启了路径压缩和按秩合并的并查集
class UnionFind {
    int n;//顶点数目
    int[] parent;//每个顶点所在连通分量的代表
    int[] size;//可以简单地理解为每个连通分量中的顶点个数
    int branchCount;// 当前连通分支数目

    public UnionFind(int n) {
    	this.n = n;
        this.branchCount = n;
        this.parent = new int[n];
        this.size = new int[n];
        Arrays.fill(size, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        // 路径压缩
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    public boolean unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        // 按秩合并
        if (size[x] < size[y]) {
            int temp = x;
            x = y;
            y = temp;
        }
        parent[y] = x;
        size[x] += size[y];
        --branchCount;
        return true;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int branchCount() {
        return branchCount;
    }
}