Union find problems
261. Graph Valid Tree
This is a typical union find problem. Notice that not only do you need to detect the loop, but also need to detect it is a connected graph.
Notice that when judge whether 2 components is connected && union 2 components together, always get to the most far parent nodes.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
32class Solution {
public int find(int[] parent, int p) {
if(parent[p] == p) return p;
return find(parent,parent[p]);
}
public boolean isConnected(int[] parent, int p, int q) {
return find(parent,p) == find(parent, q);
}
public void union(int[] parent, int p, int q) {
int index1 = find(parent, p);
int index2 = find(parent, q);
if(index1 != index2) {
parent[index1] = index2;
}
}
public boolean validTree(int n, int[][] edges) {
int[] parent = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
}
for(int[] edge:edges) {
if(isConnected(parent, edge[0], edge[1]) == true) {
return false;
}
union(parent, edge[0], edge[1]);
}
for(int i = 0; i < n; i++) {
if(!isConnected(parent, parent[i],parent[0])) return false;
}
return true;
}
}
Some problems solved by Union-find can also be solved by DFS. For example, lc200,lc547&&lc130. lc130 uses a small trick, which just set an additional node to represent the node in boundary, which can’t be transformed,then expand them into center part.