Weighted Quick-Union

 1/**
 2 * @author wangy
 3 * @version 1.0
 4 * @date 2023/5/22 / 09:04
 5 */
 6public class WeightedQuickUnion {
 7
 8    public static void main(String[] args) {
 9        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(10);
10        uf.union(4, 3);
11        uf.union(3, 8);
12        uf.union(6, 5);
13        uf.print();
14        StdOut.println(uf.find(4, 8));
15        StdOut.println(uf.find(3, 9));
16        uf.union(9, 4);
17        uf.union(2, 1);
18        uf.union(5, 0);
19        uf.print();
20        uf.union(7, 2);
21        uf.union(6, 1);
22        uf.union(7, 3);
23        uf.print();
24        StdOut.println(uf.find(2,9));
25    }
26
27}
28
29 class WeightedQuickUnionUF {
30    private int[]  id;
31    private int[]  sz;
32
33    public WeightedQuickUnionUF(int N) {
34        id = new int[N];
35        sz = new int[N];
36        for(int i = 0; i < N; i++) {
37            id[i] = i;
38            sz[i] = 1;
39        }
40    }
41    // chase parent pointers until reach root
42    // depth of i array access
43    private int root(int p){
44        while (id[p] != p) {
45            p = id[p];
46        }
47        return p;
48    }
49
50    // check p and q have the same root
51    // depth of p and q array accesses
52    public boolean find(int p, int q) {
53        return root(p) == root(q);
54    }
55
56    // change root of p to point to root of q
57    // depth of p and q array access
58    public void union(int p, int q) {
59        int i = root(p);
60        int j = root(q);
61        if (i == j) return; // already union
62        if (sz[i] > sz[j]) {
63            id[j] = i;
64            sz[i] += sz[j];
65        } else {
66            id[i] = j;
67            sz[j] += sz[i];
68        }
69    }
70
71     public void print() {
72         StdOut.println(Arrays.toString(id));
73     }
74
75}