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 | } | |
| 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 | } | |
| 23 | public boolean isSameSet(int i, int j){
| |
| 24 | return findSet(i) == findSet(j) | |
| 25 | } | |
| 26 | ||
| 27 | //return the root | |
| 28 | public int findSet(int i){
| |
| 29 | if (parent[i] == i){
| |
| 30 | return i; | |
| 31 | else | |
| 32 | parent[i] = findSet(parent[x]); | |
| 33 | return parent[i]; | |
| 34 | } | |
| 35 | } |
