DisjointSetUnion

DisjointSetUnion.java

class DisjointSetUnion {
    int[] parent;
    public DisjointSetUnion(int n) {
        parent = new int[n];
        for(int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    public int find(int x) {
        if(parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}