解題說明
Number of Provinces
題目描述:給定 n 座城市的相鄰矩陣 isConnected,isConnected[i][j]=1 表示城市 i 與 j 直接相連。求連通分量(省份)的數量。
解題思路:此題等價於求無向圖的連通分量數。可用 DFS:維護 visited 陣列,對每個未訪問的節點啟動 DFS 將整個連通分量標記,每啟動一次 DFS 省份數加一。也可用 Union-Find,每合併一次減少一個省份計數。
C++ 解法
複雜度分析
時間複雜度:O(n²) — DFS 最壞情況下訪問鄰接矩陣的每個格子;Union-Find 方法亦為 O(n²α(n)) ≈ O(n²)。
空間複雜度:O(n) — visited 陣列與遞迴呼叫堆疊最深 n 層。
虛擬碼
1. Initialize visited[0..n-1] = false, provinces = 0
2. For i from 0 to n-1:
a. If not visited[i]:
- DFS from node i: mark all reachable nodes as visited
- provinces++
3. Return provinces
DFS(node):
Mark node as visited
For each neighbor j: if connected and not visited, DFS(j)其他解法
Union-Find(並查集):初始每個城市自成一個省份,遍歷矩陣上三角合併相連城市,每次成功合併省份數減一。路徑壓縮 + 按秩合併可達近 O(1) 均攤,程式碼量略多但結構清晰。
BFS:用佇列代替遞迴,邏輯與 DFS 相同,避免深度過大時的堆疊溢出問題。
延伸思考
- 若改用鄰接串列(Adjacency List)表示圖,DFS 時間複雜度如何變化?
- 如何找出節點數最多的那個省份,並列出其所有城市?
- 若圖是有向圖(非對稱矩陣),「強連通分量」應如何求解(Kosaraju / Tarjan 演算法)?