給定
n個節點（編號0到n-1）和一組無向邊edges，回傳圖中連通分量的數量。
Example:
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2
Intuition
TIP
計算無向圖的連通分量數 — 用 DFS/BFS 遍歷或 Union-Find 合併。
- 連通分量 = 彼此可達的節點群
- DFS/BFS：從每個未訪問節點啟動遍歷，每次啟動代表一個新的連通分量
- Union-Find：合併所有邊，最後計算不同的根節點數
Approaches
1. DFS — O(V + E) / O(V + E)
- Idea: 建鄰接表，從每個未訪問節點啟動 DFS，計數啟動次數
- Time:
O(V + E) - Space:
O(V + E)
class Solution {
fun countComponents(n: Int, edges: Array<IntArray>): Int {
val graph = Array(n) { mutableListOf<Int>() }
for ((u, v) in edges) {
graph[u].add(v)
graph[v].add(u)
}
val visited = BooleanArray(n)
var count = 0
fun dfs(node: Int) {
visited[node] = true
for (next in graph[node]) {
if (!visited[next]) dfs(next)
}
}
for (i in 0 until n) {
if (!visited[i]) {
count++
dfs(i)
}
}
return count
}
}⭐ 2. Union-Find — O(E * α(n)) / O(n)
- Idea: 初始每個節點為獨立集合（共 n 個），每次成功 union 連通分量數減一
- Time:
O(E * α(n)) - Space:
O(n)
class Solution {
private lateinit var parent: IntArray
private lateinit var rank: IntArray
fun countComponents(n: Int, edges: Array<IntArray>): Int {
parent = IntArray(n) { it }
rank = IntArray(n)
var components = n
for ((u, v) in edges) {
if (union(u, v)) components--
}
return components
}
private fun find(x: Int): Int {
if (parent[x] != x) parent[x] = find(parent[x])
return parent[x]
}
private fun union(x: Int, y: Int): Boolean {
val px = find(x)
val py = find(y)
if (px == py) return false
if (rank[px] < rank[py]) parent[px] = py
else if (rank[px] > rank[py]) parent[py] = px
else { parent[py] = px; rank[px]++ }
return true
}
}🔑 Takeaways
- Pattern: 連通分量計數 — DFS 計數啟動次數 / Union-Find 計數合併次數
- Key trick: Union-Find 的
components = n - 成功 union 次數；此題是 Union-Find 的最基本應用