CSC300: Weighted Compression Halving [9/10] Previous pageContentsNext page

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
 
  public int find(int p) {
    int root = p;
    while (root != id[root]) {
      id[root] = id[id[root]];
      root = id[root];
    }



    return root;
  }

  public void union(int p, int q) {
    int pid = find(p); // loser
    int qid = find(q); // champion
    if (pid == qid) return;
    if (sz[qid] > sz[pid]) { id[pid] = qid; sz[qid] += sz[pid]; }
    else                   { id[qid] = pid; sz[pid] += sz[qid]; }
    count--;
  }

Output 

       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 4  3:  9[0, 1, 2, 4, 4, 5, 6, 7, 8, 9]
 3  8:  8[0, 1, 2, 4, 4, 5, 6, 7, 4, 9]
 6  5:  7[0, 1, 2, 4, 4, 6, 6, 7, 4, 9]
 9  4:  6[0, 1, 2, 4, 4, 6, 6, 7, 4, 4]
 2  1:  5[0, 2, 2, 4, 4, 6, 6, 7, 4, 4]
 8  9: connected
 5  0:  4[6, 2, 2, 4, 4, 6, 6, 7, 4, 4]
 7  2:  3[6, 2, 2, 4, 4, 6, 6, 2, 4, 4]
 6  1:  2[6, 2, 6, 4, 4, 6, 6, 2, 4, 4]
 1  6>  2[6, 6, 6, 4, 4, 6, 6, 2, 4, 4]
 1  0: connected
 7  6>  2[6, 6, 6, 4, 4, 6, 6, 6, 4, 4]
 6  7: connected

N=          128 Union=  0.001 [Infinity] Connected=  0.000 [     NaN]
N=          256 Union=  0.000 [   0.000] Connected=  0.000 [     NaN]
N=          512 Union=  0.000 [     NaN] Connected=  0.000 [     NaN]
N=        1,024 Union=  0.000 [     NaN] Connected=  0.000 [     NaN]
N=        2,048 Union=  0.000 [     NaN] Connected=  0.001 [Infinity]
N=        4,096 Union=  0.001 [Infinity] Connected=  0.001 [   1.000]
N=        8,192 Union=  0.001 [   1.000] Connected=  0.001 [   1.000]
N=       16,384 Union=  0.003 [   3.000] Connected=  0.002 [   2.000]
N=       32,768 Union=  0.004 [   1.333] Connected=  0.001 [   0.500]
N=       65,536 Union=  0.004 [   1.000] Connected=  0.004 [   4.000]
N=      131,072 Union=  0.011 [   2.750] Connected=  0.006 [   1.500]
N=      262,144 Union=  0.032 [   2.909] Connected=  0.015 [   2.500]
N=      524,288 Union=  0.059 [   1.844] Connected=  0.022 [   1.467]
N=    1,048,576 Union=  0.132 [   2.237] Connected=  0.063 [   2.864]
N=    2,097,152 Union=  0.327 [   2.477] Connected=  0.191 [   3.032]
N=    4,194,304 Union=  0.727 [   2.223] Connected=  0.459 [   2.403]
N=    8,388,608 Union=  1.998 [   2.748] Connected=  1.056 [   2.301]
N=   16,777,216 Union=  4.947 [   2.476] Connected=  2.554 [   2.419]
N=   33,554,432 Union= 10.013 [   2.024] Connected=  6.093 [   2.386]

Also faster

Previous pageContentsNext page