Number of Connected Components in an Undirected Graph

犯的错：1.没有check n和edges的合法性，2 按照树的bfs来写了，遇到互不相连的图时，无法完成全部遍历，应该把while循环卸载所有node遍历的for里面

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.

BFS

由于每个节点仅被发现一次，因此每个节点入栈和出栈各一次，时间均为O(1),故入栈和出栈总时间为O(V);由于需要对每个节点的邻接表进行扫描，时间为O(Adj[u]),总时间为O(E);综上所示，广度优先搜索的时间复杂度为O(V+E).即是图邻接表大小的线性函数

    class Solution {
    public int countComponents(int n, int[][] edges) {
     if( n <= 0 || edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0){ return n; }
    
    Map<Integer, Set<Integer>> graph = buildGraph(edges,n);

    Set<Integer> isVisited = new HashSet<>();

    Queue<Integer> queue = new LinkedList<>();
    int count = n;
    for(int i = 0;i<n;i++){
        if(!isVisited.contains(i)){
            queue.offer(i);
            isVisited.add(i);

            while(!queue.isEmpty()){
                int item = queue.poll();

                for(int k : graph.get(item)){
                    if(!isVisited.contains(k)){
                        queue.offer(k);
                        isVisited.add(k);
                            count--;
                    }
                }
            }
        }
    }

    return count;

}

public Map<Integer,Set<Integer>> buildGraph(int[][] edges,int n){
    Map<Integer,Set<Integer>> map = new HashMap<>();

    for(int i = 0; i < n ;i++){
        map.put(i, new HashSet<>());
    }

    for(int i = 0; i < edges.length;i++){
        int u = edges[i][0];
        int v = edges[i][1];
        map.get(u).add(v);
        map.get(v).add(u);
    }

    return map;
}
}

犯的错： while 循环里的for循环，应该循环poll出来的数对应的set，笔误写成了最外层for循环的i了，当就一个node，和谁都不连时，应该返回n