leetcode怎么计算省份数量

# 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 

复杂度分析

• 时间复杂度：O(n²) - 最坏情况下需要遍历整个矩阵
• 空间复杂度：O(n) - 用于存储访问状态和递归栈

方法二：并查集（Union-Find）

算法思路

1. 初始化：每个城市是自己的父节点
2. 遍历矩阵，合并相连的城市
3. 统计根节点的数量（即省份数量）

代码实现

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))) 

复杂度分析

• 时间复杂度：O(n² α(n)) - 其中α是反阿克曼函数，增长极其缓慢
• 空间复杂度：O(n) - 存储父节点和秩数组

方法三：广度优先搜索（BFS）

算法思路

1. 使用队列实现BFS遍历
2. 从一个城市出发，将其所有相连城市入队
3. 每次完整的BFS遍历对应一个省份

代码实现

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 

复杂度分析

• 时间复杂度：O(n²)
• 空间复杂度：O(n)

方法比较

方法	时间复杂度	空间复杂度	适用场景
DFS	O(n²)	O(n)	直观易懂，适合小规模数据
BFS	O(n²)	O(n)	需要避免递归栈溢出时使用
并查集	O(n² α(n))	O(n)	需要频繁合并查询时效率高

实际应用

这类连通性问题在实际中有广泛的应用： 1. 社交网络中的好友圈识别 2. 计算机网络中的连通区域划分 3. 图像处理中的连通区域分析 4. 推荐系统中的用户聚类

常见错误与陷阱

1. 错误理解矩阵含义：误将矩阵的行列当作城市编号（实际上行列都代表城市）
2. 重复计数：未正确标记已访问节点导致重复计算
3. 忽略自反性：忘记城市总是与自己相连（矩阵对角线总是1）
4. 对称性处理：矩阵是对称的，可以优化只遍历一半

进阶思考

1. 如何输出每个省份包含的城市？
2. 如果连接关系是动态变化的，如何高效维护省份数量？
3. 对于大规模稀疏图，如何优化存储和计算？

总结

计算省份数量问题展示了图论中连通分量计数的经典解法。DFS/BFS适合直观理解，而并查集则在需要高效合并的场景表现优异。掌握这三种方法不仅能解决LeetCode问题，也为处理实际中的连通性问题提供了通用思路。

建议读者在理解基础上，尝试用不同语言实现这些算法，并思考如何扩展到更复杂的图结构问题中。 “`

注：实际字数约1500字，可通过扩展以下内容达到1800字： 1. 添加更多示例和图示说明 2. 深入讨论并查集的优化细节 3. 添加不同语言的实现代码 4. 扩展实际应用场景的描述 5. 增加性能测试对比数据