华为 OD 训练营 · 题解精讲
LC547. 省份数量
配套讲解：视频讲解 ↗
LC547. 省份数量 视频地址：https://ntpkq.xetlk.com/s/I46D2
题目描述
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。
示例 1： MItwbXxSToays9xEQwqc49p5nud.jpg
输入： isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出： 2 示例 2： SRVNb8WyqoZbTEx96VLc6aYpnfc.jpg
输入： isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出： 3
题目解析
解题思路
本题要求统计无向图中连通块的数量，图以邻接矩阵 isConnected 给出。核心思路是遍历所有城市，对每个未被访问过的城市启动一次图遍历（DFS 或 BFS），将遍历过程中遇到的所有相连城市标记为已访问，每完成一次遍历就计数一个省份。
关键步骤
1. 初始化：获取城市数量 n，创建长度为 n 的 checkList 数组（0 表示未访问，1 表示已访问），省份计数 ans = 0。 2. 遍历所有城市：对于每个城市 i：
- 若
checkList[i] == 0，则从i开始进行遍历（DFS 或 BFS），并将checkList[i]置为 1。 - 遍历过程中，对于当前节点
x，检查所有其他节点y，若满足x != y、isConnected[x][y] == 1且checkList[y] == 0，则将y加入遍历队列/递归处理，并标记为已访问。 - 一次遍历结束后，
ans += 1。
3. 返回结果：ans 即为省份数量。
示意图（DFS 遍历过程）：
初始: checkList = [0,0,0]
i=0: 启动DFS → 标记0, 找到1相连 → 标记1 → 回溯
完成一次DFS, ans=1
i=1: checkList[1]=1, 跳过
i=2: checkList[2]=0, 启动DFS → 标记2, 无其他相连
完成一次DFS, ans=2复杂度分析
- 时间复杂度：O(n²)，需要遍历邻接矩阵的每个元素（n² 个）来检查连接关系。
- 空间复杂度：O(n)，
checkList数组占用 O(n) 空间；DFS 递归栈深度最坏 O(n)，BFS 队列最坏 O(n)。
参考代码
DFS解法
# 题目：LC547. 省份数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问
class Solution:
def dfs(self, isConnected, checkList, i):
# 对于传入的点i，将其标记为已检查过
checkList[i] = 1
# 遍历其他点j
for j in range(self.n):
# 1. 若j点未检查过 2. 与i相连 3. j和i不是同一个点
if checkList[j] == 0 and isConnected[i][j] == 1 and i != j:
# 对j进行DFS
self.dfs(isConnected, checkList, j)
def findCircleNum(self, isConnected: List[List[int]]) -> int:
# 获得城市数量
self.n = len(isConnected)
ans = 0
# 检查列表的长度是n
checkList = [0] * self.n
# 遍历每一个点i
for i in range(self.n):
# 如果该点没检查过，
if checkList[i] == 0:
# 则从点i出发，进行DFS
self.dfs(isConnected, checkList, i)
# 做完本次DFS，省份数量+1
ans += 1
return ans
BFS解法
# 题目：LC547. 省份数量
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
ans = 0
# 获得城市数量
n = len(isConnected)
# 检查列表的长度是n
checkList = [0] * n
# 遍历每一个点i
for i in range(n):
if checkList[i] == 0: # 若未i检查过
q = deque([i]) # 把i加入q中，作为BFS的起始位置
checkList[i] = 1 # 将i标记为已检查过
while(q): # 从i开始，进行BFS
x = q.popleft() # 弹出q队头的点x，考虑与其相连的点y
for y in range(n): # 遍历其他点y，若y点未检查过，且与x相连
if x != y and checkList[y] == 0 and isConnected[x][y] == 1:
q.append(y) # 则把y加入队列中
checkList[y] = 1 # 同时把y标记为已检查过
# 完成本次BFS，省份（连通块）数量+1
ans += 1
return ans