并查集(DSU)中兩種提高算法效率的方法：path compression && union-by-rank.

1.path compression

If a node we are visiting is not a root node of a tree, then we modify the structure of the tree to make sure this node and all of its ancestor nodes(except the root node) share the root node as their common parent node. Just like the illustration shows:

public int find(int x) {
	if(x != parent[x]) {
   		parent[x] = find(parent[x]);
   	}
    return parent[x];
}
           

2.union-by-rank

Here the rank just means the height of a tree.

Each time we invoke the function union(int x, int y), we will firstly find two root nodes xr and yr. If xr is not equal to yr, then we will do the union.

We always comply to the following principle:

Let the node having the higher rank be the parent node of the other node, if the two nodes have the same rank, we randomly choose one node to be the parent node of the other, and the rank of the node which becomes the parent node increases by 1.

public boolean union(int x, int y) {
    int xr = find(x);
    int yr = find(y);
    if(xr == yr) {
        return false;
    }else{
        if(rank[xr] < rank[yr]) {
            parent[xr] = yr; 
        }else if(rank[xr] > rank[yr]) {
            parent[yr] = xr;
        }else{
            parent[yr] = xr;
            rank[xr]++;
        }
        return true;
    }
}
           

3.The complete DSU code:

class DSU {
    private int[] parent;
    private int[] rank;
    
    public DSU(int N) {
        parent = new int[N];
        rank = new int[N];
        
        for(int i = 0; i < N; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public boolean union(int x, int y) {
        int xr = find(x);
        int yr = find(y);
        if(xr == yr) {
            return false;
        }else{
            if(rank[xr] < rank[yr]) {
                parent[xr] = yr; 
            }else if(rank[xr] > rank[yr]) {
                parent[yr] = xr;
            }else{
                parent[yr] = xr;
                rank[xr]++;
            }
            return true;
        }
    }
}