323 Number of Connected Components in an Undirected Graph

323. Number of Connected Components in an Undirected Graph​
1. Question
Givennnodes labeled from0ton - 1and 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
     0          3
2
     |          |
3
     1 --- 2    4
Copied!
Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2.
Example 2:
1
     0           4
2
     |           |
3
     1 --- 2 --- 3
Copied!
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1.
Note:
You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.
2. Implementation
(1) BFS
1
class Solution {
2
    public int countComponents(int n, int[][] edges) {
3
        if (n <= 1) {
4
            return n;
5
        }
6
​
7
        // BFS
8
        List<Set<Integer>> adjList = new ArrayList<>();
9
        for (int i = 0; i < n; i++) {
10
            adjList.add(new HashSet<>());
11
        }
12
​
13
        for (int[] edge : edges) {
14
            adjList.get(edge[0]).add(edge[1]);
15
            adjList.get(edge[1]).add(edge[0]);
16
        }
17
​
18
        boolean[] visited = new boolean[n];
19
        int count = 0;
20
​
21
        for (int i = 0; i < n; i++) {
22
            if (!visited[i]) {
23
                ++count;
24
                Queue<Integer> queue = new LinkedList<>();
25
                queue.add(i);
26
​
27
                while (!queue.isEmpty()) {
28
                    int curIndex = queue.remove();
29
                    visited[curIndex] = true;
30
​
31
                    for (int nextIndex : adjList.get(curIndex)) {
32
                        if (!visited[nextIndex]) {
33
                            queue.add(nextIndex);
34
                        }
35
                    }
36
                }
37
            }
38
        }
39
        return count;
40
    }
41
}
Copied!
(2) DFS
1
class Solution {
2
    public int countComponents(int n, int[][] edges) {
3
        if (n <= 1) {
4
            return n;
5
        }
6
​
7
        List<Set<Integer>> adjList = new ArrayList<>();
8
​
9
        for (int i = 0; i < n; i++) {
10
            adjList.add(new HashSet<>());
11
        }
12
​
13
        boolean[] visited = new boolean[n];
14
​
15
        for (int[] edge : edges) {
16
            adjList.get(edge[0]).add(edge[1]);
17
            adjList.get(edge[1]).add(edge[0]);
18
        }
19
​
20
        int count = 0;
21
​
22
        for (int i = 0; i < n; i++) {
23
            if (!visited[i]) {
24
                ++count;
25
​
26
                searchComponentByDFS(i, adjList, visited);
27
            }
28
        }
29
        return count;
30
    }
31
​
32
    public void searchComponentByDFS(int node, List<Set<Integer>> adjList, boolean[] visited) {
33
        visited[node] = true;
34
​
35
        for (int nextNode : adjList.get(node)) {
36
            if (!visited[nextNode]) {
37
                searchComponentByDFS(nextNode, adjList, visited);
38
            }
39
        }
40
    }
41
}
Copied!
(3) Union Find
1
class Solution {
2
    public int countComponents(int n, int[][] edges) {
3
        if (n <= 1) {
4
            return n;
5
        }
6
​
7
        UnionFind uf = new UnionFind(n);
8
​
9
        for (int[] edge : edges) {
10
            uf.union(edge[0], edge[1]);
11
        }
12
        return uf.count;
13
    }
14
​
15
    class UnionFind {
16
        int[] sets;
17
        int[] size;
18
        int count;
19
​
20
        public UnionFind(int n) {
21
            sets = new int[n];
22
            size = new int[n];
23
            count = n;
24
​
25
            for (int i = 0; i < n; i++) {
26
                sets[i] = i;
27
                size[i] = 1;
28
            }
29
        }
30
​
31
        public int find(int node) {
32
            while (node != sets[node]) {
33
                node = sets[node];
34
            }
35
            return node;
36
        }
37
​
38
        public void union(int i, int j) {
39
            int node1 = find(i);
40
            int node2 = find(j);
41
​
42
            if (node1 == node2) {
43
                return;
44
            }
45
​
46
            if (size[node1] < size[node2]) {
47
                sets[node1] = node2;
48
                size[node2] += size[node2];
49
            }
50
            else {
51
                sets[node2] = node1;
52
                size[node1] += size[node2];
53
            }
54
            --count;
55
        }
56
    }
57
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度O(n)，空间复杂度O(n)
DFS: 时间复杂度O(n)，空间复杂度O(n)
Union Find: 时间复杂度O(n), 空间复杂度O(n)

329 Longest Increasing Path in a Matrix

332 Reconstruct Itinerary

Last modified 2yr ago

Copy link

Contents

323. Number of Connected Components in an Undirected Graph

1. Question

2. Implementation

3. Time & Space Complexity

323. Number of Connected Components in an Undirected Graph​

1. Question

2. Implementation

3. Time & Space Complexity

323. Number of Connected Components in an Undirected Graph