Unites the sets containing elements x and y. Uses union by rank to attach the smaller tree under the larger tree. @param x the first element @param y the second element
(int x, int y)
| 63 | * @param y the second element |
| 64 | */ |
| 65 | public void union(int x, int y) { |
| 66 | int r0 = find(x); |
| 67 | int r1 = find(y); |
| 68 | |
| 69 | if (r1 == r0) { |
| 70 | return; |
| 71 | } |
| 72 | |
| 73 | // Union by rank |
| 74 | if (r[r0] > r[r1]) { |
| 75 | p[r1] = r0; |
| 76 | } else if (r[r1] > r[r0]) { |
| 77 | p[r0] = r1; |
| 78 | } else { |
| 79 | p[r1] = r0; |
| 80 | r[r0]++; |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | /** |
| 85 | * Counts the number of disjoint sets. |