您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode怎么计算省份数量
## 问题背景
在LeetCode题库中，第547题「省份数量」（Number of Provinces）是一个经典的图论问题，常用于考察并查集（Union-Find）和深度优先搜索（DFS）的应用。该问题的描述如下：
> 有n个城市，其中一些城市彼此相连（直接或通过其他城市间接相连）。我们称这种连接关系为"省份"。现在给定一个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(n²) | O(n) | 直观易懂，适合小规模数据 |
| BFS | O(n²) | O(n) | 需要避免递归栈溢出时使用 |
| 并查集 | O(n² α(n)) | O(n) | 需要频繁合并查询时效率高 |
这类连通性问题在实际中有广泛的应用： 1. 社交网络中的好友圈识别 2. 计算机网络中的连通区域划分 3. 图像处理中的连通区域分析 4. 推荐系统中的用户聚类
计算省份数量问题展示了图论中连通分量计数的经典解法。DFS/BFS适合直观理解，而并查集则在需要高效合并的场景表现优异。掌握这三种方法不仅能解决LeetCode问题，也为处理实际中的连通性问题提供了通用思路。
建议读者在理解基础上，尝试用不同语言实现这些算法，并思考如何扩展到更复杂的图结构问题中。 “`
注：实际字数约1500字，可通过扩展以下内容达到1800字： 1. 添加更多示例和图示说明 2. 深入讨论并查集的优化细节 3. 添加不同语言的实现代码 4. 扩展实际应用场景的描述 5. 增加性能测试对比数据
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。