-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathGraphValidTree.java
More file actions
72 lines (58 loc) · 1.57 KB
/
GraphValidTree.java
File metadata and controls
72 lines (58 loc) · 1.57 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
68
69
70
71
72
class Solution {
public boolean validTree(int n, int[][] edges) {
if(n == 0) return true;
UnionFind uf = new UnionFind(n);
for(int[] pair : edges){
if(!uf.connected(pair[0], pair[1])){
uf.union(pair[0], pair[1]);
} else {
return false;
}
}
return uf.getRoots() == 1;
}
class UnionFind {
int id[];
int size[];
public UnionFind(int n){
id = new int[n];
size = new int[n];
for(int i=0; i < n; i++){
id[i] = i;
size[i] = 1;
}
}
public int root(int i){
while(i != id[id[i]]){
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public boolean connected(int p, int q){
return root(p) == root(q);
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
/* Link small tree below large */
if(size[i] < size[j]){
id[i] = j;
size[j] += size[i];
} else {
id[j] = i;
size[i] += size[j];
}
}
public int getRoots(){
int[] roots = new int[id.length];
int count = 0;
for(int i=0; i < id.length; i++){
int rt = root(i);
if(roots[rt] == 0) count++;
roots[rt] = 1;
}
return count;
}
}
}