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.

LintCode 类似题：Find the Connected Component in the Undirected Graph

http://www.jiuzhang.com/solutions/find-the-connected-component-in-the-undirected-graph/

Tips:

• 解法1：并查集（UNION-FIND)

  for(int[] edge : edges) 查找每个edge两边的nodes的father，如果发现还没有合并，就Union，把第一个的father设为第二个，即map.put(fa_x, fa_y);

  用n来代表最后的联通块个数，所以合并一次就要n--。最后返回n即可。

• 解法2：DFS

• 解法3：BFS

Code:

解法1（并查集）：

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 1) {
            return n;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, i);
        }
        for (int[] edge : edges) {
            int fa_x = find(map, edge[0]);
            int fa_y = find(map, edge[1]);
            if (fa_x != fa_y) {
                map.put(fa_x, fa_y);
                n--;
            }
        }
        return n;
    }

    private int find(HashMap<Integer, Integer> map, int x) {
        int father = map.get(x);
        while (father != map.get(father)) {
            father = map.get(father);
        }
        return father;
    }    
}

Union Find 模板：

HashMap<Integer, Integer> map = new HashMap<>();

int find(HashMap<Integer, Integer> map, int x) {
     int father = map.get(x);
        while (father != map.get(father)) {
            father = map.get(father);
        }
     return father;
}

void union(int x, int y) {
    int fa_x = find(map, edge[0]);
    int fa_y = find(map, edge[1]);
    if (fa_x != fa_y) {
       map.put(fa_x, fa_y);
    }
}

解法2（DFS）：

  public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 1)
            return n;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            map.get(edge[0]).add(edge[1]);
            map.get(edge[1]).add(edge[0]);
        }
        Set<Integer> visited = new HashSet<>();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (visited.add(i)) {
                dfsVisit(i, map, visited);
                count++;
            }
        }
        return count;
    }

    private void dfsVisit(int i, Map<Integer, List<Integer>> map, Set<Integer> visited) {
        for (int j : map.get(i)) {
            if (visited.add(j))
                dfsVisit(j, map, visited);
        }
    }
}

解法3（BFS）：

 public class Solution {

    public int countComponents(int n, int[][] edges) {
        if (n <= 1) {
            return n;
        }
        List<List<Integer>> adjList = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<Integer>());
        }
        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++;
                Queue<Integer> queue = new LinkedList<Integer>();
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int index = queue.poll();
                    visited[index] = true;
                    for (int next : adjList.get(index)) {
                        if (!visited[next]) {
                            queue.offer(next);
                        }
                    }
                }
            }
        }

        return count;
    }
}