# LeetCode怎么計算省份數量
## 問題背景
在LeetCode題庫中，第547題「省份數量」（Number of Provinces）是一個經典的圖論問題，常用于考察并查集（Union-Find）和深度優先搜索（DFS）的應用。該問題的描述如下：
> 有n個城市，其中一些城市彼此相連（直接或通過其他城市間接相連）。我們稱這種連接關系為"省份"?，F在給定一個n x n的矩陣`isConnected`表示城市之間的連接關系，其中`isConnected[i][j] = 1`表示第i個城市和第j個城市直接相連，`isConnected[i][j] = 0`表示不相連。要求計算總共有多少個"省份"。
## 問題理解
這個問題可以抽象為**無向圖的連通分量計數**問題：
- 每個城市是圖中的一個節點
- 城市之間的連接是圖中的邊
- "省份"就是圖中的連通分量
例如：
輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 輸出：2 解釋：城市0和1相連形成一個省份，城市2自己是一個省份
## 解決方案
### 方法一：深度優先搜索（DFS）
#### 算法思路
1. 將城市看作圖中的節點，連接關系看作邊
2. 從一個未被訪問的城市開始，遞歸訪問所有相連的城市
3. 每次完整的DFS遍歷就找到一個連通分量（省份）
#### 代碼實現
```python
def findCircleNum(isConnected):
n = len(isConnected)
visited = [False] * n
count = 0
def dfs(city):
for neighbor in range(n):
if isConnected[city][neighbor] == 1 and not visited[neighbor]:
visited[neighbor] = True
dfs(neighbor)
for city in range(n):
if not visited[city]:
count += 1
visited[city] = True
dfs(city)
return count
def findCircleNum(isConnected):
n = len(isConnected)
parent = [i for i in range(n)]
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # 路徑壓縮
x = parent[x]
return x
def union(x, y):
rootX = find(x)
rootY = find(y)
if rootX != rootY:
parent[rootX] = rootY
for i in range(n):
for j in range(i+1, n):
if isConnected[i][j] == 1:
union(i, j)
return len(set(find(i) for i in range(n)))
def findCircleNum(isConnected):
n = len(isConnected)
parent = [i for i in range(n)]
rank = [1] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # 路徑壓縮
return parent[x]
def union(x, y):
rootX = find(x)
rootY = find(y)
if rootX != rootY:
if rank[rootX] > rank[rootY]: # 按秩合并
parent[rootY] = rootX
elif rank[rootX] < rank[rootY]:
parent[rootX] = rootY
else:
parent[rootY] = rootX
rank[rootX] += 1
for i in range(n):
for j in range(i+1, n):
if isConnected[i][j] == 1:
union(i, j)
return len(set(find(i) for i in range(n)))
from collections import deque
def findCircleNum(isConnected):
n = len(isConnected)
visited = [False] * n
count = 0
for city in range(n):
if not visited[city]:
count += 1
queue = deque([city])
visited[city] = True
while queue:
current = queue.popleft()
for neighbor in range(n):
if isConnected[current][neighbor] == 1 and not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return count
| 方法 | 時間復雜度 | 空間復雜度 | 適用場景 |
|---|---|---|---|
| DFS | O(n2) | O(n) | 直觀易懂，適合小規模數據 |
| BFS | O(n2) | O(n) | 需要避免遞歸棧溢出時使用 |
| 并查集 | O(n2 α(n)) | O(n) | 需要頻繁合并查詢時效率高 |
這類連通性問題在實際中有廣泛的應用： 1. 社交網絡中的好友圈識別 2. 計算機網絡中的連通區域劃分 3. 圖像處理中的連通區域分析 4. 推薦系統中的用戶聚類
計算省份數量問題展示了圖論中連通分量計數的經典解法。DFS/BFS適合直觀理解，而并查集則在需要高效合并的場景表現優異。掌握這三種方法不僅能解決LeetCode問題，也為處理實際中的連通性問題提供了通用思路。
建議讀者在理解基礎上，嘗試用不同語言實現這些算法，并思考如何擴展到更復雜的圖結構問題中。 “`
注：實際字數約1500字，可通過擴展以下內容達到1800字： 1. 添加更多示例和圖示說明 2. 深入討論并查集的優化細節 3. 添加不同語言的實現代碼 4. 擴展實際應用場景的描述 5. 增加性能測試對比數據
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
