This approach is similar to simply DFS. Total runtime worst runtime complexity is O(N) (best case each component consists of 1 node, worst case is there is 1 component.

- Generate HashMap to access edges in
`O(1)`

time - Created array of flags whether each node is visited
- Use simply DFS to mark all connected nodes as marked and increment result, if current starting node is not visited yet

Runtime Complexity: `O(N)`

Space Complexity: `O(N^2)`

(worst case: every node is connected to every other node), it can be avoided by reusing input `edges`

, but then runtime will be `O(N * K)`

, where `K`

is number of edges.

```
public class Solution {
public int countComponents(int n, int[][] edges) {
//generate map to constant acces of edges outgoing from point
HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for(int[] a : edges) {
if(!map.containsKey(a[0])) {
map.put(a[0], new ArrayList<Integer>());
}
if(!map.containsKey(a[1])) {
map.put(a[1], new ArrayList<Integer>());
}
//bidirectional
map.get(a[0]).add(a[1]);
map.get(a[1]).add(a[0]);
}
boolean[] visited = new boolean[n];
int res = 0;
for(int i = 0; i < n; i++) {
if(!visited[i]) {
greedy(map, i, visited);
res++;
}
}
return res;
}
void greedy(HashMap<Integer, List<Integer>> map, int source, boolean[] visited) {
if(visited[source]) {
return;
}
visited[source] = true;
//no connections
if(!map.containsKey(source)) {
return;
}
for(int a : map.get(source)) {
greedy(map, a, visited);
}
}
}
```