SHOW:
|
|
- or go back to the newest paste.
| 1 | Union-find Disjoint Sets | |
| 2 | ||
| 3 | public UnionFind(int N){
| |
| 4 | parent = new int[N]; | |
| 5 | rank = new int[N]; //all 0 | |
| 6 | numSets = N; | |
| 7 | for (int i = 0; i < N; i++){
| |
| 8 | parent[i] = i; | |
| 9 | - | } |
| 9 | + | } |
| 10 | } | |
| 11 | public void unionSet(int i, int j){
| |
| 12 | if (!isSameSet(i, j)){ numSets--;
| |
| 13 | int x = findSet(i), y = findSet(j); //root of i and j | |
| 14 | // rank is used to keep the tree short | |
| 15 | if (rank[x] > rank[y]) | |
| 16 | parent[y] = x; | |
| 17 | else | |
| 18 | parent[x] = y; | |
| 19 | if (rank [x] == rank[y]) | |
| 20 | rank[y]++; | |
| 21 | } | |
| 22 | } |
