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:
Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]
0 3
| |
1 --- 2 4
Output: 2
Example 2:
Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
0 4
| |
1 --- 2 --- 3
Output: 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.
代码
Approach #1 DFS
class Solution {
public int countComponents(int n, int[][] edges) {
if (n <= 1) return n;
Map<Integer, List<Integer>> map = new HashMap();
for (int i = 0; i < n; i++) {
map.put(i, new ArrayList());
}
for (int[] edge: edges) {
map.get(edge[0]).add(edge[1]);
map.get(edge[1].add(edge[0]));
}
Set<Integer> visited = new HashSet();
int count = 0;
for (int i = 0; i < n; i++) {
if (visited.add(i)) {
dfs(i, map, visited);
count++;
}
}
return count;
}
private void dfs(int i, Map<Integer, List<Integer>> map, Set<Integer> visited) {
for (int j : map.get(i)) {
if (visited.add(j)) {
dfs(j, map, visited);
}
}
}
}