LeetCode 547. 省份数量

字数 2272 2025-10-26 09:00:52

LeetCode 547. 省份数量

题目描述
有 n 个城市，其中一些城市彼此相连（即它们是直接相连的，或通过其他相连的城市间接相连）。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected 表示城市的连接关系，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。你需要计算矩阵中表示的所有城市中，总共有多少个"省份"。

解题过程

问题理解与抽象
- 这个问题的核心是找出一个图中"连通分量"的数量。在这个问题中：
  - 节点 (Node): 每一个城市就是一个节点。
  - 边 (Edge): 如果 isConnected[i][j] = 1，则表示节点 i 和节点 j 之间存在一条无向边。
  - 连通分量 (Connected Component): 一个省份就是一个连通分量，即一组节点，其中任意两个节点之间都有路径相连，并且这组节点不与组外的任何节点相连。
- 题目给出的矩阵 isConnected 是一个"邻接矩阵"。例如，对于3个城市：
```
isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]
```
  - 城市0和城市1相连（isConnected[0][1] = 1）。
  - 城市0和城市2不相连（isConnected[0][2] = 0）。
  - 城市1和城市2不相连（isConnected[1][2] = 0）。
  - 因此，城市0和1构成一个省份，城市2自己构成一个省份。总共有2个省份。
核心思路：深度优先搜索 (DFS)
- 我们可以从任意一个尚未被访问过的城市开始，"探索"所有它能到达的城市。一次完整的探索过程，就相当于发现了一个省份（一个连通分量）。
- 具体步骤：
  - 步骤一：初始化。 我们创建一个数组 visited，长度为 n（城市数量），初始值全部为 false。这个数组用来记录哪些城市已经被访问过，避免重复计算和无限循环。同时，初始化省份计数器 count 为 0。
  - 步骤二：遍历每个城市。 我们从第 0 个城市开始，逐个检查每个城市。
  - 步骤三：发现新省份。 如果当前城市 i 还没有被访问过（visited[i] == false），这意味着我们发现了一个新的、尚未被探索的省份。于是我们：
    1. 将省份计数器 count 加 1。
    2. 从这个城市 i 开始，执行 深度优先搜索 (DFS)，去"标记"这个省份里所有的城市。
  - 步骤四：深度优先搜索 (DFS) 过程。 DFS 的目的是遍历一个连通分量中的所有节点。
    1. 首先，将当前城市 cur 标记为已访问（visited[cur] = true）。
    2. 然后，我们检查当前城市 cur 的所有邻居城市。具体做法是遍历 isConnected[cur] 这一行。
    3. 对于每一个其他城市 j，如果满足两个条件：
      a. isConnected[cur][j] == 1（表示城市 cur 和城市 j 直接相连）。
      b. visited[j] == false（表示城市 j 还未被访问过）。
    4. 我们就以城市 j 为新的起点，递归地调用 DFS 函数。这个过程会一直深入，直到当前路径上所有相连的城市都被访问。
  - 步骤五：汇总结果。 当遍历完所有城市后，省份计数器 count 的值就是最终答案。
举例说明
我们以 isConnected = [[1,1,0],[1,1,0],[0,0,1]] 为例，模拟算法过程：
- 初始化：visited = [false, false, false], count = 0。
- 检查城市0：未被访问。发现新省份，count 变为 1。
  - 开始DFS(0)：
    - 标记 visited[0] = true。
    - 检查城市0的邻居：isConnected[0][1] 是1，且城市1未被访问，递归调用DFS(1)。
      - 在DFS(1)中：
        
        标记 visited[1] = true。
        
        检查城市1的邻居：isConnected[1][0] 是1，但城市0已访问过，跳过。isConnected[1][2] 是0，跳过。
      - DFS(1)结束。
    - 检查城市0的邻居：isConnected[0][2] 是0，跳过。
  - DFS(0)结束。至此，省份1（包含城市0和1）探索完毕。
- 检查城市1：已被访问（在探索省份1时访问过了），跳过。
- 检查城市2：未被访问。发现新省份，count 变为 2。
  - 开始DFS(2)：
    - 标记 visited[2] = true。
    - 检查城市2的邻居：isConnected[2][0] 是0，跳过；isConnected[2][1] 是0，跳过。
  - DFS(2)结束。省份2（只包含城市2）探索完毕。
- 所有城市检查完毕，返回 count = 2。
关键点与总结
- 核心思想： 使用 DFS（或 BFS，广度优先搜索）来遍历图中的连通分量。每次从一个未访问节点开始的完整遍历，就对应一个连通分量。
- visited 数组的重要性： 它确保了每个节点只会被处理一次，避免了重复计数和程序陷入无限递归循环。
- 时间复杂度： O(n²)，因为最坏情况下我们需要检查邻接矩阵中的每一个元素。
- 空间复杂度： O(n)，主要用于 visited 数组和递归调用栈的深度（在最坏情况下，栈深度为 n）。

LeetCode 547. 省份数量题目描述有 n 个城市，其中一些城市彼此相连（即它们是直接相连的，或通过其他相连的城市间接相连）。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected 表示城市的连接关系，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。你需要计算矩阵中表示的所有城市中，总共有多少个"省份"。解题过程问题理解与抽象这个问题的核心是找出一个图中"连通分量"的数量。在这个问题中：节点 (Node): 每一个城市就是一个节点。边 (Edge): 如果 isConnected[i][j] = 1 ，则表示节点 i 和节点 j 之间存在一条无向边。连通分量 (Connected Component): 一个省份就是一个连通分量，即一组节点，其中任意两个节点之间都有路径相连，并且这组节点不与组外的任何节点相连。题目给出的矩阵 isConnected 是一个"邻接矩阵"。例如，对于3个城市：城市0和城市1相连（ isConnected[0][1] = 1 ）。城市0和城市2不相连（ isConnected[0][2] = 0 ）。城市1和城市2不相连（ isConnected[1][2] = 0 ）。因此，城市0和1构成一个省份，城市2自己构成一个省份。总共有2个省份。核心思路：深度优先搜索 (DFS) 我们可以从任意一个尚未被访问过的城市开始，"探索"所有它能到达的城市。一次完整的探索过程，就相当于发现了一个省份（一个连通分量）。具体步骤：步骤一：初始化。我们创建一个数组 visited ，长度为 n（城市数量），初始值全部为 false 。这个数组用来记录哪些城市已经被访问过，避免重复计算和无限循环。同时，初始化省份计数器 count 为 0。步骤二：遍历每个城市。我们从第 0 个城市开始，逐个检查每个城市。步骤三：发现新省份。如果当前城市 i 还没有被访问过（ visited[i] == false ），这意味着我们发现了一个新的、尚未被探索的省份。于是我们：将省份计数器 count 加 1。从这个城市 i 开始，执行深度优先搜索 (DFS) ，去"标记"这个省份里所有的城市。步骤四：深度优先搜索 (DFS) 过程。 DFS 的目的是遍历一个连通分量中的所有节点。首先，将当前城市 cur 标记为已访问（ visited[cur] = true ）。然后，我们检查当前城市 cur 的所有邻居城市。具体做法是遍历 isConnected[cur] 这一行。对于每一个其他城市 j ，如果满足两个条件： a. isConnected[cur][j] == 1 （表示城市 cur 和城市 j 直接相连）。 b. visited[j] == false （表示城市 j 还未被访问过）。我们就以城市 j 为新的起点，递归地调用 DFS 函数。这个过程会一直深入，直到当前路径上所有相连的城市都被访问。步骤五：汇总结果。当遍历完所有城市后，省份计数器 count 的值就是最终答案。举例说明我们以 isConnected = [[1,1,0],[1,1,0],[0,0,1]] 为例，模拟算法过程：初始化： visited = [false, false, false] , count = 0 。检查城市0：未被访问。发现新省份， count 变为 1。开始DFS(0)：标记 visited[0] = true 。检查城市0的邻居： isConnected[0][1] 是1，且城市1未被访问，递归调用DFS(1)。在DFS(1)中：标记 visited[1] = true 。检查城市1的邻居： isConnected[1][0] 是1，但城市0已访问过，跳过。 isConnected[1][2] 是0，跳过。 DFS(1)结束。检查城市0的邻居： isConnected[0][2] 是0，跳过。 DFS(0)结束。至此，省份1（包含城市0和1）探索完毕。检查城市1：已被访问（在探索省份1时访问过了），跳过。检查城市2：未被访问。发现新省份， count 变为 2。开始DFS(2)：标记 visited[2] = true 。检查城市2的邻居： isConnected[2][0] 是0，跳过； isConnected[2][1] 是0，跳过。 DFS(2)结束。省份2（只包含城市2）探索完毕。所有城市检查完毕，返回 count = 2 。关键点与总结核心思想：使用 DFS（或 BFS，广度优先搜索）来遍历图中的连通分量。每次从一个未访问节点开始的完整遍历，就对应一个连通分量。 visited 数组的重要性：它确保了每个节点只会被处理一次，避免了重复计数和程序陷入无限递归循环。时间复杂度： O(n²)，因为最坏情况下我们需要检查邻接矩阵中的每一个元素。空间复杂度： O(n)，主要用于 visited 数组和递归调用栈的深度（在最坏情况下，栈深度为 n）。