Medium
Given n nodes labeled from ``0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
0 3
| |
1 --- 2 4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.
Example 2:
0 4
| |
1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as[1, 0] and thus will not appear together in edges.
這道題主要是為了復(fù)習(xí)一下Union Find這個數(shù)據(jù)結(jié)構(gòu)，三部分寫好Union Find: int[] father, int find(), void union().
class Solution {
public int[] father;
public int countComponents(int n, int[][] edges) {
if (edges == null || edges.length == 0 || edges[0].length == 0){
return n;
}
father = new int[n];
int res = n;
for (int i = 0; i < n; i++){
father[i] = i;
}
for (int i = 0; i < edges.length; i++){
int u = edges[i][0];
int v = edges[i][1];
if (find(u) != find(v)){
union(u, v);
res--;
}
}
return res;
}
private int find(int a){
if (father[a] == a){
return a;
}
return find(father[a]);
}
private void union(int a, int b){
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b){
father[root_a] = root_b;
}
}
}
