Quick-Union

 1/**
 2 * @author wangy
 3 * @version 1.0
 4 * @date 2023/5/22 / 08:59
 5 */
 6public class QuickUnion {
 7
 8    public static void main(String[] args) {
 9        QuickUnionUF uf = new QuickUnionUF(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
29class QuickUnionUF {
30    private int[] id;
31
32    QuickUnionUF(int N) {
33        id = new int[N];
34        for (int i = 0; i < N; i++) {
35            id[i] = i;
36        }
37    }
38
39    // chase parent pointers until reach root
40    // depth of i array access
41    private int root(int p) {
42        while (id[p] != p) {
43            p = id[p];
44        }
45        return p;
46    }
47
48    // check p and q have the same root
49    // depth of p and q array accesses
50    public boolean find(int p, int q) {
51        return root(p) == root(q);
52    }
53
54    // change root of p to point to root of q
55    // depth of p and q array access
56    public void union(int p, int q) {
57        int rp = root(p);
58        int rq = root(q);
59        id[rp] = rq;
60    }
61
62    public void print() {
63        StdOut.println(Arrays.toString(id));
64    }
65}
66
67