本文完整拆解 LeetCode 323 Number of Connected Components 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Number of Connected Components 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1
Constraints:
1 <= n <= 20001 <= edges.length <= 5000edges[i].length == 20 <= ai <= bi < nai != bi- There are no repeated edges.
Python
# time complexity: O(V + E * α(n)) is the inverse Ackermann function
# space complexity: O(V)
from typing import List
class UnionFind():
def __init__(self, n):
self.parents = [i for i in range(n)]
self.rank = [0 for _ in range(n)]
def find(self, node):
while node != self.parents[node]:
node = self.parents[node]
return node
def uion(self, nodeX, nodeY):
parentX = self.find(nodeX)
parentY = self.find(nodeY)
if parentX == parentY:
return
if self.rank[parentX] > self.rank[parentY]:
self.parents[parentY] = self.parents[parentX]
elif self.rank[parentX] < self.rank[parentY]:
self.parents[parentX] = self.parents[parentY]
else:
self.parents[parentX] = self.parents[parentY]
self.rank[parentY] += 1
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
disjointUnionSet = UnionFind(n)
for startVertex, endVertex in edges:
disjointUnionSet.uion(startVertex, endVertex)
parent = set()
for i in range(n):
parent.add(disjointUnionSet.find(i))
return len(set(parent))
n = 4
edges = [[0, 1], [2, 3], [1, 2]]
print(Solution().countComponents(n, edges))
Number of Connected Components in an Undirected Graph 解題思路
計算無向圖的連通分量,最直接的想法是:從每個還沒走訪過的節點出發做一次 DFS,能走到的都屬於同一塊,走完就代表找到一個分量。另一個等價解法是並查集——一開始每個節點自成一塊,每合併一條邊成功就把分量數減一。
Number of Connected Components in an Undirected Graph 演算法步驟
- 用鄰接表建圖,建立長度 n 的 visited 陣列。
- 走訪 0 到 n-1 的每個節點。
- 若尚未走訪,計數器加一,並從該節點做一次 DFS 把整塊標記為已訪。
- 所有節點處理完後回傳計數器。
Number of Connected Components in an Undirected Graph 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(V+E) |
| 空間複雜度 | O(V+E) |
建圖需要走訪所有邊,DFS 總共走訪每個節點與每條邊各一次,時間為 O(V+E)。鄰接表佔 O(V+E),visited 與遞迴堆疊佔 O(V)。並查集版本時間接近 O(E α(V))。
Number of Connected Components in an Undirected Graph 的邊界情況與常見錯誤
- 孤立節點(沒有任何邊)本身就是一個分量,不能漏算。
- 無向邊要在鄰接表的兩端都加入。
- 邊的清單可能為空,此時答案等於節點數 n。
- 並查集版本記得做路徑壓縮,否則會退化。
Number of Connected Components in an Undirected Graph 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| 對每個節點跑一次 BFS | O(V+E) | O(V+E) | 與 DFS 等價 |
| 並查集 | O(E α(V)) | O(V) | 適合邊會動態加入的情境 |
| 鄰接表 + DFS | O(V+E) | O(V+E) | 本文採用 |


