L 323. Number of Connected Components in an Undirected Graph ---M

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.

A:

典型的图遍历，  dfs

public class Solution {
    public int countComponents(int n, int[][] edges) {
        int res = 0;
        boolean A[] = new boolean[n];
        Map<Integer, List<Integer>> map  = new HashMap();
        for(int i =0;i<n;i++)
            map.put(i,new LinkedList());
        for(int i =0;i<edges.length;i++){
            map.get(edges[i][0]).add(edges[i][1]);
            map.get(edges[i][1]).add(edges[i][0]);
        }
        for(int i =0;i<n;i++){
            if(A[i] == false){
                A[i] = true;
                res++;
                dfs(i,map, A);
            }
        }
        return res;
    }
    private void dfs(int root, Map<Integer, List<Integer>> map, boolean[] A){
        List<Integer> list = map.get(root);
        for(Integer cur : list){
            if(A[cur]==false){
                A[cur] = true;
                dfs(cur, map,A);
            }
        }
    }
}
 

Mistakes: