/*     * 323.Number of Connected Components in an Undirected Graph     * 2016-4-2 by Mingyang     * 这个题目自己也是花了一段时间，自己的思路是先构建一个HashMap，每个值对应一个相邻边的list，然后根据list的长度的大小，如果为0表示res++     * 如果为1加到queue里面去，再一个一个的取消和自己的通路，像有向图那样，从list里面remove掉！结果发现行不通，万一很多点都是两个list 长度     * 那么就没法，所以我现在回归无向图的基本方法，就是用boolean记录访问过没，每到一个点就visited 为true，然后他会进去把自己的所有的相邻边     * 全部感染，访问。最后再跳出来。BFS很好的例子！！！     */     public int countComponents(int n, int[][] edges) {            if (n <= 1) {                return n;            }            List
     
      
       > adjList = new ArrayList
       
        
         >();            for (int i = 0; i < n; i++) {                adjList.add(new ArrayList
         
          ());            }            for (int[] edge : edges) {                adjList.get(edge[0]).add(edge[1]);                adjList.get(edge[1]).add(edge[0]);            }            boolean[] visited = new boolean[n];            int count = 0;            for (int i = 0; i < n; i++) {                if (!visited[i]) {                    count++;                    dfs(visited, i, adjList);                }            }            return count;        }        public void dfs(boolean[] visited, int index, List
          
           
            > adjList) { visited[index] = true; for (int i : adjList.get(index)) { if (!visited[i]) { dfs(visited, i, adjList); } } }
           
          
         
        
       
      
     

 不过还是Union Find要简单一些

private int[] father;public int countComponents(int n, int[][] edges) {    Set
     
       set = new HashSet
      
       ();    father = new int[n];    for (int i = 0; i < n; i++) {        father[i] = i;    }    for (int i = 0; i < edges.length; i++) {         union(edges[i][0], edges[i][1]);    }    for (int i = 0; i < n; i++){         set.add(find(i));    }    return set.size();}int find(int node) {    if (father[node] == node) {        return node;    }    father[node] = find(father[node]);    return father[node];}void union(int node1, int node2) {    father[find(node1)] = find(node2);}