算法（Algorithms）第4版 练习 1.5.12

package com.qiusongde;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UFQuickUnionPathCom {

    private int[] id;//save the site's parent link(site indexed)
    private int count;//number of components
    
    public UFQuickUnionPathCom(int n) {
        
        count = n;
        
        id = new int[n];
        for(int i = 0; i < n; i++)
            id[i] = i;
        
    }
    
    public int count() {
        return count;
    }
    
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    
    //adding a loop to link every site on the path 
    //from p to the root directly to the root
    public int find(int p) {
        
        int root = p;//initialize root
        
        //find root(id[p] save the parent of p)
        while(root != id[root])
            root = id[root];
        
        //link every site from p to root to root
        while(id[p] != root) {//parent isn't root
            int nextp = id[p];
            id[p] = root;//link directly to root
            p = nextp;
        }
        
        return root;
    }
    
    public void union(int p, int q) {
        
        int pRoot = find(p);//find pRoot
        int qRoot = find(q);//find qRoot
        
        if(pRoot == qRoot)
            return;
        
        id[pRoot] = qRoot;
        count--;
    }
    
    @Override
    public String toString() {
        String s = "";
        
        for(int i = 0; i < id.length; i++) {
            s += id[i] + " ";
        }
        s += "
" + count + " components";
        
        return s;
    }
    
    public static void main(String[] args) {
        
        //initialize N components
        int N = StdIn.readInt();
        UFQuickUnionPathCom uf = new UFQuickUnionPathCom(N);
        StdOut.println(uf);
        
        while(!StdIn.isEmpty()) {
            
            int p = StdIn.readInt();
            int q = StdIn.readInt();
            
            if(uf.connected(p, q)) {//ignore if connected
                StdOut.println(p + " " + q + " is connected");
                continue;
            }
            
            uf.union(p, q);//connect p and q
            StdOut.println(p + " " + q);
            StdOut.println(uf);
        }
        
    }

}

测试：

0 1 2 3 4 5 6 7 8 9 
10 components
4 3
0 1 2 3 3 5 6 7 8 9 
9 components
3 8
0 1 2 8 3 5 6 7 8 9 
8 components
6 5
0 1 2 8 3 5 5 7 8 9 
7 components
9 4
0 1 2 8 8 5 5 7 8 8 
6 components
2 1
0 1 1 8 8 5 5 7 8 8 
5 components
8 9 is connected
5 0
0 1 1 8 8 0 5 7 8 8 
4 components
7 2
0 1 1 8 8 0 5 1 8 8 
3 components
6 1
1 1 1 8 8 0 0 1 8 8 
2 components
1 0 is connected
6 7 is connected

输入序列：

10

0 1

1 2

2 3

0 1 2 3 4 5 6 7 8 9 
10 components
0 1
1 1 2 3 4 5 6 7 8 9 
9 components
1 2
1 2 2 3 4 5 6 7 8 9 
8 components
2 3
1 2 3 3 4 5 6 7 8 9 
7 components

 这样产生了长度为4的路径0->1->2->3。