CSC300 / CSC402: Compression [6/9]

  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;
    id[pid] = qid;

    count--;
  }

Output

       10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 4  3:  9[0, 1, 2, 3, 3, 5, 6, 7, 8, 9]
 3  8:  8[0, 1, 2, 8, 3, 5, 6, 7, 8, 9]
 6  5:  7[0, 1, 2, 8, 3, 5, 5, 7, 8, 9]
 4  8>  7[0, 1, 2, 8, 8, 5, 5, 7, 8, 9]
 9  4:  6[0, 1, 2, 8, 8, 5, 5, 7, 8, 8]
 2  1:  5[0, 1, 1, 8, 8, 5, 5, 7, 8, 8]
 8  9: connected
 5  0:  4[0, 1, 1, 8, 8, 0, 5, 7, 8, 8]
 7  2:  3[0, 1, 1, 8, 8, 0, 5, 1, 8, 8]
 6  0>  3[0, 1, 1, 8, 8, 0, 0, 1, 8, 8]
 6  1:  2[1, 1, 1, 8, 8, 0, 0, 1, 8, 8]
 1  0: connected
 6  1>  2[1, 1, 1, 8, 8, 0, 1, 1, 8, 8]
 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.002 [Infinity] Connected=  0.001 [   1.000]
N=       16,384 Union=  0.003 [   1.500] Connected=  0.001 [   1.000]
N=       32,768 Union=  0.004 [   1.333] Connected=  0.001 [   1.000]
N=       65,536 Union=  0.004 [   1.000] Connected=  0.003 [   3.000]
N=      131,072 Union=  0.011 [   2.750] Connected=  0.005 [   1.667]
N=      262,144 Union=  0.026 [   2.364] Connected=  0.011 [   2.200]
N=      524,288 Union=  0.040 [   1.538] Connected=  0.021 [   1.909]
N=    1,048,576 Union=  0.136 [   3.400] Connected=  0.084 [   4.000]
N=    2,097,152 Union=  0.487 [   3.581] Connected=  0.285 [   3.393]
N=    4,194,304 Union=  1.331 [   2.733] Connected=  0.534 [   1.874]
N=    8,388,608 Union=  2.383 [   1.790] Connected=  1.201 [   2.249]
N=   16,777,216 Union=  6.689 [   2.807] Connected=  2.797 [   2.329]
N=   33,554,432 Union= 16.546 [   2.474] Connected=  7.270 [   2.599]

Both operations logarithmic