并查集

并查集

class UnionFind {
    private final int[] fa; // 代表元
    private final int[] size; // 大小
    public int cc; // 连通块个数

    UnionFind(int n) {
        fa = new int[n];
        for (int i = 0; i < n; ++i) {
            fa[i] = i;
        }
        size = new int[n];
        Arrays.fill(size, 1);
        cc = n;
    }

    /* 返回x所在集合的代表元 */
    /* 同时做路径压缩 */
    public int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);
        }
        return fa[x];
    }

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

    public boolean merge(int from, int to) {
        int x = find(from);
        int y = find(to);
        if (x == y) {
            return false;
        }
        fa[x] = y;
        size[y] += size[x];
        cc--;
        return true;
    }

    public int getSize(int x) {
        return size[find(x)];
    }
}

简单来说并查集的作用就是把点按连通块分开