Description

323. Number of Connected Components in an Undirected Graph 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.

## Java DFS solution

TODO: try out a faster solution.

``````class Solution {
public int countComponents(int n, int[][] edges) {
HashSet<Integer> unvisited = new HashSet<>();
for (int i=0; i<n; i++) {
}

HashMap<Integer, List<Integer>> hm = new HashMap<>();
for (int[] edge : edges) {
if (hm.containsKey(edge)) {
} else {
hm.put(edge, new ArrayList<Integer>());
}
if (hm.containsKey(edge)) {
} else {
hm.put(edge, new ArrayList<Integer>());
}
}

int ret=0;
while (unvisited.size()!=0) {
ret++;
int node = 0;
for (int tmp : unvisited) {
node = tmp;
break;
}
dfs(unvisited, hm, node);
}

return ret;
}

private void dfs(HashSet<Integer> unvisited, HashMap<Integer, List<Integer>> hm, int node) {
unvisited.remove(node);
if (!hm.containsKey(node))  return;
for (int neighbor : hm.get(node)) {
if (unvisited.contains(neighbor)) {
dfs(unvisited, hm, neighbor);
}
}
}
}

`````` Runtime: around 25ms