Repository navigation
Expand file tree
/
Copy pathDisjoinSetUnionByRank.java
More file actions
67 lines (55 loc) · 1.7 KB
/
Copy pathDisjoinSetUnionByRank.java
File metadata and controls
67 lines (55 loc) · 1.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package com.hellokoding.datastructure;
public class DisjoinSetUnionByRank {
int[] parents, ranks;
int N;
DisjoinSetUnionByRank(int N) {
this.N = N;
parents = new int[N];
ranks = new int[N];
initDisjoinSet();
}
void initDisjoinSet() {
for (int i = 0; i < N; i++) {
parents[i] = i;
}
}
int findRoot(int x) {
if (parents[x] != x) {
parents[x] = findRoot(parents[x]);
}
return parents[x];
}
void union(int x, int y) {
int rootOfX = findRoot(x);
int rootOfY = findRoot(y);
if (rootOfX == rootOfY) {
return;
}
if (ranks[rootOfX] < ranks[rootOfY]) {
parents[rootOfX] = rootOfY;
} else if (ranks[rootOfX] > ranks[rootOfY]) {
parents[rootOfY] = rootOfX;
} else {
parents[rootOfX] = rootOfY;
ranks[rootOfY] = ranks[rootOfY] + 1;
}
}
public static void main(String[] args) {
int N = 4;
DisjoinSetUnionByRank disjoinSet = new DisjoinSetUnionByRank(N);
disjoinSet.union(0, 1);
disjoinSet.union(1, 2);
// Check if 1 is in the same set with 2
if (disjoinSet.findRoot(1) == disjoinSet.findRoot(2)) {
System.out.println("1 is in the same set with 2");
} else {
System.out.println("1 is not in the same set with 2");
}
// Check if 1 is in the same set with 3
if (disjoinSet.findRoot(1) == disjoinSet.findRoot(3)) {
System.out.println("1 is in the same set with 3");
} else {
System.out.println("1 is not in the same set with 3");
}
}
}