323. Number of Connected Components in an Undirected Graph

corner case: pay attention when there are no edges at all and there are only one node!

A DFS way to do it: first construct the graph to List of list and we mark and traverse. Count the number of times traversing the graph!

Run Time: O(N)

public class Solution {
    // a dfs way to count connected components 
    public int countComponents(int n, int[][] edges) {
        if(n <= 1)return n;
        HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
        for(int i = 0; i < n; i++) {
            map.put(i, new ArrayList<>());
        }
        //build the map
        for(int[] arr: edges){
            map.get(arr[0]).add(arr[1]);
            map.get(arr[1]).add(arr[0]);
        }
        //count the number of times performing the dfs
        boolean[] visited = new boolean[n];
        int count = 0;
        for(int i = 0;i < n;i++){
            if(!visited[i]){
                dfs(map,i,visited);
                count++;
            }
        }
        return count;
    }
    public void dfs(HashMap<Integer,List<Integer>> map,int start,boolean[] visited){
        if(visited[start] == true)return;
        //traverse its neighbors
        visited[start] = true;
        for(int adj: map.get(start)){
            dfs(map,adj,visited);
        }
    }
}