Union-find Disjoint Sets

public UnionFind(int N){
    parent = new int[N];
    rank = new int[N]; //all 0
    numSets = N;
    for (int i = 0; i < N; i++){
        parent[i] = i;
    }
}
public void unionSet(int i, int j){
    if (!isSameSet(i, j)){ numSets--;
        int x = findSet(i),  y = findSet(j); //root of i and j
        // rank is used to keep the tree short
        if (rank[x] > rank[y])
            parent[y] = x;
        else
            parent[x] = y;
        if (rank [x] == rank[y])
            rank[y]++;
    }
}
public boolean isSameSet(int i, int j){
    return findSet(i) == findSet(j)
}

//return the root
public int findSet(int i){
    if (parent[i] == i){
        return i;
    else
        parent[i] = findSet(parent[x]);
        return parent[i];
    }
}