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++) {
            unvisited.add(i);
        }
        
        HashMap<Integer, List<Integer>> hm = new HashMap<>();
        for (int[] edge : edges) {
            if (hm.containsKey(edge[0])) {
                hm.get(edge[0]).add(edge[1]);
            } else {
                hm.put(edge[0], new ArrayList<Integer>());
                hm.get(edge[0]).add(edge[1]);
            }
            if (hm.containsKey(edge[1])) {
                hm.get(edge[1]).add(edge[0]);
            } else {
                hm.put(edge[1], new ArrayList<Integer>());
                hm.get(edge[1]).add(edge[0]);
            }            
        }
        
        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);
            }
        }
    }
}


imgRuntime: around 25ms