LeetCode 题解工作台
省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnec…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们创建一个数组 ，用于记录每个城市是否被访问过。 接下来，遍历每个城市 ，如果该城市未被访问过，则从该城市开始深度优先搜索，通过矩阵 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个省，然后对这些城市继续深度优先搜索，直到同一个省的所有城市都被访问到，即可得到一个省，将答案 加 ，然后遍历下一个未被访问过的城市，直到遍历完所有的城市。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3
提示：
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]为1或0isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
解题思路
方法一：DFS
我们创建一个数组 ，用于记录每个城市是否被访问过。
接下来，遍历每个城市 ，如果该城市未被访问过，则从该城市开始深度优先搜索，通过矩阵 得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个省，然后对这些城市继续深度优先搜索，直到同一个省的所有城市都被访问到，即可得到一个省，将答案 加 ，然后遍历下一个未被访问过的城市，直到遍历完所有的城市。
最后返回答案即可。
时间复杂度 ，空间复杂度 。其中 是城市的数量。
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i: int):
vis[i] = True
for j, x in enumerate(isConnected[i]):
if not vis[j] and x:
dfs(j)
n = len(isConnected)
vis = [False] * n
ans = 0
for i in range(n):
if not vis[i]:
dfs(i)
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n^2) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
They want connected components, not shortest paths, because the question asks for grouped cities rather than route length.
- question_mark
The adjacency matrix format hints that scanning rows directly is expected, so building another graph structure is often unnecessary overhead.
- question_mark
If they ask for DFS, BFS, and Union Find trade-offs, they are checking whether you can recognize equivalent component-counting strategies on the same input.
常见陷阱
外企场景- error
Incrementing the province count for every connected edge instead of for every new unvisited starting city gives the wrong answer.
- error
Forgetting indirect connectivity leads to under-grouping, especially when city 0 connects to 1 and city 1 connects to 2.
- error
Revisiting cities because visited is marked too late can cause repeated work or infinite recursion on dense parts of the matrix.
进阶变体
外企场景- arrow_right_alt
Return the actual province members instead of only the count by collecting cities during each DFS.
- arrow_right_alt
Switch the input from an adjacency matrix to an edge list, which changes neighbor lookup and usually favors adjacency lists or Union Find.
- arrow_right_alt
Handle dynamic connection updates, where Union Find becomes more attractive than rerunning full DFS after each merge.