.jpg)
871 字
4 分钟
省份数量
.png)
题目描述
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
解题思路
- 图论建模：
- 将城市视为节点，连接关系视为边
- 问题转化为求无向图的连通分量数量
- 深度优先搜索 (DFS)：
- 从每个未访问城市出发递归标记连通城市
- 统计DFS启动次数即为省份数量
- 广度优先搜索 (BFS)：
- 使用队列迭代访问连通城市
- 同样统计BFS启动次数
- 并查集 (Union-Find)：
- 初始化每个城市为独立集合
- 合并相连城市，最后统计根节点数量
- 邻接矩阵利用：
- 直接使用输入矩阵避免额外存储
关键洞察
- 连通分量本质：
- 省份等价于图的连通分量
- 矩阵对称性：
- 邻接矩阵对称，可优化遍历范围
- 访问标记：
- 避免重复访问同一城市
- 对角线处理：
- 对角线恒为1（城市自身连接）
- 高效合并：
- 并查集路径压缩优化性能
- 空间优化：
- 直接修改访问标记减少空间占用
复杂度分析
| 指标 | DFS/BFS | 并查集 |
|---|---|---|
| 时间复杂度 | O(n²) : 遍历整个矩阵 | O(n² α(n)) : 近似线性 |
| 空间复杂度 | O(n) : 访问标记数组 | O(n) : 父节点存储 |
| 最优情况 | O(n) : 全连通图 | O(n α(n)) : 合并次数少 |
| 最坏情况 | O(n²) : 稀疏连接 | O(n² α(n)) : 完全遍历 |
代码实现
JavaScript 版本 (DFS)
const findCircleNum = (isConnected) => { const n = isConnected.length; const visited = new Array(n).fill(false); let provinces = 0;
const dfs = (i) => { visited[i] = true; for (let j = 0; j < n; j++) { if (isConnected[i][j] === 1 && !visited[j]) { dfs(j); } } };
for (let i = 0; i < n; i++) { if (!visited[i]) { provinces++; dfs(i); } }
return provinces;};Rust 版本 (并查集)
struct UnionFind { parent: Vec<usize>, count: usize,}
impl UnionFind { fn new(n: usize) -> Self { let parent = (0..n).collect(); UnionFind { parent, count: n } }
fn find(&mut self, x: usize) -> usize { if self.parent[x] != x { self.parent[x] = self.find(self.parent[x]); } self.parent[x] }
fn union(&mut self, x: usize, y: usize) { let root_x = self.find(x); let root_y = self.find(y); if root_x != root_y { self.parent[root_y] = root_x; self.count -= 1; } }}
impl Solution { pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 { let n = is_connected.len(); let mut uf = UnionFind::new(n); for i in 0..n { for j in (i + 1)..n { if is_connected[i][j] == 1 { uf.union(i, j); } } } uf.count as i32 }}Python 版本 (BFS)
from collections import deque
class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: n = len(isConnected)
visited = [False] * n provinces = 0
for i in range(n): if not visited[i]: provinces += 1 queue = deque([i]) visited[i] = True
while queue: city = queue.popleft() for neighbor in range(n): if isConnected[city][neighbor] == 1 and not visited[neighbor]: visited[neighbor] = True queue.append(neighbor) return provinces实际应用场景
- 社交网络：计算用户社交圈数量`
- 网络运维：检测服务器集群连通性`
- 城市规划：计算城市群数量`
- 生物信息学：蛋白质相互作用网络分析`