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)