-
Notifications
You must be signed in to change notification settings - Fork 0
/
323.java
46 lines (46 loc) · 1.25 KB
/
323.java
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
public class Solution {
public class UnionFind{
public int conponent;
int[] height;
int[] parent;
public UnionFind(int n){
parent=new int[n];
height=new int[n];
for(int i=0;i<n;i++){
parent[i]=i;
}
conponent=n;
}
public boolean find(int i, int j){
return findRoot(i)==findRoot(j);
}
public int findRoot(int i){
while(i!=parent[i]) i=parent[i];
return i;
}
public void connect(int i, int j){
i=findRoot(i);
j=findRoot(j);
if(i==j) return;
if(height[i]>height[j]){
parent[j]=i;
}
else if(height[i]<height[j]){
parent[i]=j;
}
else{
parent[i]=j;
height[j]++;
}
//System.out.println("i= "+i+" "+"j= "+j+" "+"rootI= "+rootI+" "+"rootJ= "+rootJ);
conponent--;
}
}
public int countComponents(int n, int[][] edges) {
UnionFind wf=new UnionFind(n);
for(int[] e : edges){
wf.connect(e[0], e[1]);
}
return wf.conponent;
}
}