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:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

0          3
|          |
1 --- 2    4 

Output: 2
Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

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

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

Solution

  1. Union Find
    使用了基本最原始的并查集代码,其中对find和union均做了优化。这种方法效率最高
  2. DFS
  3. BFS

Code

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
public int countComponents(int n, int[][] edges) {
if(edges == null || edges.length == 0) return n;
int[] parent = new int[n];
int[] rank = new int[n];
for(int i = 0; i < n; i++) parent[i] = i;
for(int i = 0; i < edges.length; i++){
union(parent, rank, edges[i][0], edges[i][1]);
}
int res = 0;
for(int i = 0; i < n; i++)
if(parent[i] == i) res++;
return res;
}

public void union(int[] parent, int[] rank, int x , int y){
int xr = find(parent, x); int yr = find(parent, y);
if(rank[xr] == rank[yr]){
parent[yr] = xr;
rank[xr]++;
}else if(rank[xr] > rank[yr]){
parent[yr] = xr;
}else{
parent[xr] = yr;
}
}

public int find(int[] parent, int x){
if(parent[x] != x){
parent[x] = find(parent, parent[x]);
}
return parent[x];
}


public int countComponents1(int n, int[][] edges) {
if(edges == null || edges.length == 0) return n;
List<List<Integer>> g = new ArrayList<>();
for(int i = 0; i < n; i++) g.add(new ArrayList<>());
for(int i = 0; i < edges.length; i++){
g.get(edges[i][0]).add(edges[i][1]);
g.get(edges[i][1]).add(edges[i][0]);
}

int res = 0; int[] visited = new int[n];
for(int i = 0; i < n; i++){
if(visited[i] == 0){
res++;
dfs(visited, i, g);
}
}
return res;
}

public void dfs(int[] visited, int v, List<List<Integer>> g){
if(visited[v] == 1) return;

visited[v] = 1;
for(Integer neighbor : g.get(v)){
dfs(visited, neighbor, g);
}
}


public int countComponents2(int n, int[][] edges) {
if(edges == null || edges.length == 0) return n;
List<List<Integer>> g = new ArrayList<>();
for(int i = 0; i < n; i++) g.add(new ArrayList<>());
for(int i = 0; i < edges.length; i++){
g.get(edges[i][0]).add(edges[i][1]);
g.get(edges[i][1]).add(edges[i][0]);
}

int res = 0; int[] visited = new int[n];
for(int i = 0; i < n; i++){
if(visited[i] == 0){
res++;
bfs(visited, i, g);
}
}
return res;
}

public void bfs(int[] visited, int v, List<List<Integer>> g){
Deque<Integer> q = new ArrayDeque<>();
q.add(v);
visited[v] = 1;
while(!q.isEmpty()){
int x = q.poll();
for(int neighbor : g.get(x)){
if(visited[neighbor] == 0){
visited[neighbor] = 1;
q.offer(neighbor);
}
}
}
}

并查集类的实现

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
public class UnionFindSet{
int[] parent;
int[] rank;

public UnionFindSet(int n){
parent = new int[n];
for(int i = 0; i < n; i++) parent[i] = i;
rank = new int[n];
}

public int find(int x){ // Path Compression
if (x != parent[x]){
parent[x] = find(parent[x]);
}
return parent[x];
}

public boolean union(int x, int y){// Weighted
int xr = find(x); int yr = find(y);
if(xr == yr) return false;
if(rank[xr] == rank[yr]){
parent[yr] = xr;
rank[xr]++;
}else if(rank[xr] > rank[yr])
parent[yr] = xr;
else
parent[xr] = yr;
return true;
}
}