CSC300: Weighted Compression [8/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])
      root = id[root];
    while (id[p] != root) {
      int newp = id[p];
      id[p] = root;
      p = newp;
    }
    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.001 [   1.000] Connected=  0.000 [     NaN]
N=          512 Union=  0.000 [   0.000] Connected=  0.000 [     NaN]
N=        1,024 Union=  0.000 [     NaN] Connected=  0.001 [Infinity]
N=        2,048 Union=  0.000 [     NaN] Connected=  0.000 [   0.000]
N=        4,096 Union=  0.000 [     NaN] Connected=  0.001 [Infinity]
N=        8,192 Union=  0.001 [Infinity] 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.002 [   1.000]
N=       65,536 Union=  0.003 [   0.750] Connected=  0.003 [   1.500]
N=      131,072 Union=  0.009 [   3.000] Connected=  0.007 [   2.333]
N=      262,144 Union=  0.018 [   2.000] Connected=  0.010 [   1.429]
N=      524,288 Union=  0.055 [   3.056] Connected=  0.026 [   2.600]
N=    1,048,576 Union=  0.172 [   3.127] Connected=  0.073 [   2.808]
N=    2,097,152 Union=  0.434 [   2.523] Connected=  0.255 [   3.493]
N=    4,194,304 Union=  0.991 [   2.283] Connected=  0.482 [   1.890]
N=    8,388,608 Union=  1.682 [   1.697] Connected=  0.937 [   1.944]
N=   16,777,216 Union=  4.240 [   2.521] Connected=  2.861 [   3.053]
N=   33,554,432 Union=  8.646 [   2.039] Connected=  5.419 [   1.894]

Even faster

Previous pageContentsNext page