CSC300 / CSC402: Weighted [5/9] 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];





    return root;
  }

  public void union(int p, int q) {
    int pid = find(p); // champion, unless q is bigger
    int qid = find(q); // loser, unless p is smaller
    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  0: connected
 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.000 [   0.000]
N=        8,192 Union=  0.001 [   1.000] Connected=  0.001 [Infinity]
N=       16,384 Union=  0.002 [   2.000] Connected=  0.002 [   2.000]
N=       32,768 Union=  0.003 [   1.500] Connected=  0.002 [   1.000]
N=       65,536 Union=  0.004 [   1.333] Connected=  0.003 [   1.500]
N=      131,072 Union=  0.008 [   2.000] Connected=  0.008 [   2.667]
N=      262,144 Union=  0.022 [   2.750] Connected=  0.016 [   2.000]
N=      524,288 Union=  0.052 [   2.364] Connected=  0.043 [   2.687]
N=    1,048,576 Union=  0.189 [   3.635] Connected=  0.127 [   2.953]
N=    2,097,152 Union=  0.499 [   2.640] Connected=  0.427 [   3.362]
N=    4,194,304 Union=  0.841 [   1.685] Connected=  0.743 [   1.740]
N=    8,388,608 Union=  2.091 [   2.486] Connected=  1.724 [   2.320]
N=   16,777,216 Union=  4.793 [   2.292] Connected=  4.576 [   2.654]
N=   33,554,432 Union=  9.952 [   2.076] Connected=  9.855 [   2.154]

Both operations logarithmic

Previous pageContentsNext page