島嶼問題#
經典題目：島嶼數量 (LeetCode 200)#
題目：給定二維網格，'1' 為陸地，'0' 為水域。計算島嶼數量。
規則：四連通（上下左右），對角線不算相連。
輸入：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
輸出：3（三個島嶼）解法一：染色法 (Flood Fill)#
核心思想#
發現一座島嶼時，將其「沉沒」（標記為已訪問），避免重複計算。
演算法步驟#
- 走訪整個網格
- 遇到
'1'時，島嶼數量 +1 - 用 DFS/BFS 將整座島嶼標記為
'0'
DFS 實作
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
# 邊界檢查 + 是否為陸地
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # 沉島
# 四個方向擴散
dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count方向陣列技巧：使用
dx = [-1, 1, 0, 0],dy = [0, 0, -1, 1]簡化四方向走訪。
副作用：直接修改 grid 會破壞原始資料。若不允許修改，需使用額外的
visited陣列。
解法二：並查集 (Union-Find)#
核心思想#
將相鄰的陸地合併到同一集合，最終集合數量即為島嶼數量。
演算法步驟#
- 初始化：每個
'1'單獨成集 - 走訪網格：相鄰的
'1'執行 Union - 統計最終集合數量
關鍵實作#
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.count = 0
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路徑壓縮
return self.parent[x]
def union(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
self.count -= 1 # 合併時計數減 1座標轉換：2D 座標
(i, j)轉為 1D 索引：i * cols + j
兩種解法比較#
| 特性 | Flood Fill | Union-Find |
|---|---|---|
| 時間複雜度 | O(M × N) | O(M × N × α) |
| 空間複雜度 | O(M × N) 遞迴堆疊 | O(M × N) |
| 是否修改原圖 | 是（可避免） | 否 |
| 適用場景 | 一次性查詢 | 動態連通性 |
選擇建議：
- 簡單題目 → Flood Fill（程式碼簡潔）
- 需要多次查詢連通性 → Union-Find
變體：朋友圈 (LeetCode 547)#
題目：N×N 鄰接矩陣表示 N 人的好友關係，求朋友圈數量。
本質：與島嶼問題相同，都是求連通分量數量。
差異：
- 島嶼問題：網格上的空間相鄰
- 朋友圈：節點間的邏輯連接
def findCircleNum(M):
n = len(M)
uf = UnionFind(n)
uf.count = n # 初始每人獨立
for i in range(n):
for j in range(i + 1, n):
if M[i][j] == 1:
uf.union(i, j)
return uf.count