323. 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:

1
2
3
0          3
|          |
1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

1
2
3
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.

解法1：Union-Find

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] root = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        for (int[] edge : edges) {
            int root1 = find(root, edge[0]);
            int root2 = find(root, edge[1]);
            if (root1 != root2) {
                root[root1] = root2;
                n--;
            }
        }
        return n;
    }
    private int find(int[] root, int id) {
        while (root[id] != id) {
            id = root[id];
        }
        return id;
    }
}

解法2：DFS

DFS统计visited的node的个数的一种办法是，维护visited的set，每次执行一次dfs，然后到下一个节点如果没有visit过就++count。最后count就是总的visited的分隔的group的个数。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (edges == null || edges.length == 0 || edges[0].length == 0) {
            return n;
        }
        int count = 0;
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();    // store the edges
        for (int[] edge : edges) {
            if (!map.containsKey(edge[0])) {
                map.put(edge[0], new ArrayList<Integer>());
            }
            map.get(edge[0]).add(edge[1]);
            if (!map.containsKey(edge[1])) {
                map.put(edge[1], new ArrayList<Integer>());
            }
            map.get(edge[1]).add(edge[0]);
        }
        Set<Integer> visited = new HashSet<Integer>();  // visited nodes
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                count++;
                dfs(visited, i, map);             
            }
        }
        return count;
    }
    private void dfs(Set<Integer> visited, int current, Map<Integer, List<Integer>> map) {
        visited.add(current);   // add to visited node list
        if (!map.containsKey(current)) {
            return;
        }
        List<Integer> list = map.get(current);
        for (int node : list) {
            if (!visited.contains(node)) {
                dfs(visited, node, map);            
            }
        }
        return;
    }
}