Quick-Find

 1/**
 2 * @author wangy
 3 * @version 1.0
 4 * @date 2023/5/22 / 08:42
 5 */
 6
 7public class QuickFind {
 8
 9    public static void main(String[] args) {
10        QuickFindUF uf = new QuickFindUF(10);
11        uf.union(4, 3);
12        uf.union(3, 8);
13        uf.union(6, 5);
14        uf.print();
15        StdOut.println(uf.find(4,8));
16        StdOut.println(uf.find(3,9));
17        uf.union(9,4);
18        uf.union(2,1);
19        uf.union(5,0);
20        uf.print();
21        uf.union(7,2);
22        uf.union(6,1);
23        uf.union(7,3);
24        uf.print();
25    }
26
27}
28
29class QuickFindUF {
30
31    private int[] id;
32
33    // set id of each object to itself
34    // N array access
35    public QuickFindUF(int N) {
36        id = new int[N];
37        for (int i = 0; i < N; i++) {
38            id[i] = i;
39        }
40    }
41
42    // check p and q are in the same component
43    // 2 array access
44    public boolean find(int p, int q) {
45        return id[p] == id[q];
46    }
47
48    // change all entries of id[p] to id[q]
49    // at most 2N +2 array access
50    public void union(int p, int q) {
51        int pid = id[p];
52        int qid = id[q];
53        for (int i = 0; i < id.length; i++) {
54            if (id[i] == pid) {
55                id[i] = qid;
56            }
57        }
58    }
59
60    public void print() {
61        StdOut.println(Arrays.toString(id));
62    }
63
64}