547. 省份数量

547. 省份数量

题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。

如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected，其中：

  • isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连
  • isConnected[i][j] = 0 表示二者不直接相连

返回矩阵中 省份的数量。

示例 1

text
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2

text
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

约束

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 0 或 1
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

核心思路

这题本质上是在问：

  • 图里有多少个 连通块

因为：

  • 一个省份，就是一组彼此连通的城市
  • 省份数量，就是连通分量数量

所以这题至少有两种非常经典的做法：

  • 解法一：DFS / BFS 遍历连通块（推荐先理解）
  • 解法二：并查集（推荐掌握）

先理解：为什么这是图问题？

每个城市都可以看成一个节点。

如果：

text
isConnected[i][j] = 1

就说明：

  • 节点 i 和节点 j 之间有边

所以整个矩阵描述的其实就是一个无向图。

而题目问的“省份数量”，就是：

  • 图里一共有多少块彼此独立的连接区域

也就是连通分量个数。

解法一：DFS 遍历连通块

这是最直观、最适合第一次理解的做法。

思路拆解

我们维护一个 visited 数组，表示每个城市有没有被访问过。

然后从 0 到 n - 1 依次扫描：

  • 如果某个城市还没访问过
  • 说明发现了一个新的省份
  • 于是省份数量 +1
  • 然后从这个城市出发做 DFS，把和它连通的所有城市全部标记掉

这样每触发一次 DFS，就对应找到一个新的省份。

一步一步写出算法

第一步：定义访问数组

ts
const visited = new Array(n).fill(false)

第二步：定义 DFS

ts
const dfs = (city: number): void => {
    visited[city] = true

    for (let next = 0; next < n; next++) {
        if (isConnected[city][next] === 1 && !visited[next]) {
            dfs(next)
        }
    }
}

第三步：遍历所有城市

ts
let provinces = 0

for (let city = 0; city < n; city++) {
    if (!visited[city]) {
        provinces++
        dfs(city)
    }
}

第四步：返回答案

ts
return provinces

代码实现（TypeScript）

ts
function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length
    const visited = new Array(n).fill(false)

    const dfs = (city: number): void => {
        visited[city] = true

        for (let next = 0; next < n; next++) {
            if (isConnected[city][next] === 1 && !visited[next]) {
                dfs(next)
            }
        }
    }

    let provinces = 0
    for (let city = 0; city < n; city++) {
        if (!visited[city]) {
            provinces++
            dfs(city)
        }
    }

    return provinces
}

复杂度分析

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

因为输入本身就是一个 n x n 矩阵。

这一解法的优缺点

优点：

  • 最容易理解
  • 和“连通块计数”本质直接对应

缺点：

  • 递归写法依赖调用栈

解法二：并查集

这是图连通性问题的经典做法。

思路拆解

并查集的核心思想是：

  • 把属于同一个连通块的城市合并到同一个集合里

开始时：

  • 每个城市各自是一个独立集合

然后遍历矩阵：

  • 如果 isConnected[i][j] === 1
  • 就把 i 和 j 合并

最后剩下多少个集合，就是多少个省份。

一步一步写出算法

第一步：初始化并查集

ts
const parent = Array.from({ length: n }, (_, i) => i)

表示每个点一开始的父节点都是自己。

第二步：定义 find

ts
const find = (x: number): number => {
    if (parent[x] !== x) {
        parent[x] = find(parent[x])
    }
    return parent[x]
}

这里用了路径压缩。

第三步：定义 union

ts
const union = (a: number, b: number): void => {
    const rootA = find(a)
    const rootB = find(b)
    if (rootA !== rootB) {
        parent[rootA] = rootB
        count--
    }
}

第四步：遍历矩阵做合并

因为矩阵是对称的，只需要遍历上三角即可：

ts
for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
        if (isConnected[i][j] === 1) {
            union(i, j)
        }
    }
}

第五步：返回集合数量

ts
return count

代码实现（TypeScript）

ts
function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length
    const parent = Array.from({ length: n }, (_, i) => i)
    let count = n

    const find = (x: number): number => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    const union = (a: number, b: number): void => {
        const rootA = find(a)
        const rootB = find(b)
        if (rootA !== rootB) {
            parent[rootA] = rootB
            count--
        }
    }

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (isConnected[i][j] === 1) {
                union(i, j)
            }
        }
    }

    return count
}

复杂度分析

  • 时间复杂度：O(n^2 * α(n))
  • 空间复杂度：O(n)

其中 α(n) 是阿克曼函数的反函数，增长极慢，可以近似看成常数。

这一解法的优缺点

优点：

  • 是连通性问题经典模板
  • 很适合面试扩展

缺点：

  • 对第一次做图题的人不如 DFS 直观

两种解法对比

解法时间复杂度空间复杂度特点
DFS 连通块O(n^2)O(n)最直观
并查集O(n^2 * α(n))O(n)模板性强

如果你是第一次做这题，建议先理解 DFS；如果你在整理图论模板，并查集一定要掌握。

手动模拟一遍

以：

text
isConnected = [[1,1,0],[1,1,0],[0,0,1]]

为例。

城市关系

  • 0 和 1 连通
  • 2 自己单独一组

所以图里有两个连通块：

text
{0,1}
{2}

DFS 过程

先看城市 0：

  • 没访问过，所以发现一个新省份
  • 从 0 出发 DFS
  • 会把 0 和 1 都标记掉

接着看城市 1：

  • 已访问，跳过

再看城市 2：

  • 没访问过，所以发现第二个省份

最终答案就是：

text
2

面试时最容易错的点

1. 这题求的是连通块数量

不是问有多少条边，也不是问某两个城市是否相连。

2. 矩阵是对称的，表示无向图

因为：

text
isConnected[i][j] == isConnected[j][i]

所以 i 连 j，就等价于 j 连 i。

3. 并查集遍历上三角就够了

否则会重复处理边。

4. DFS / BFS 都可以做

这里只是我选了 DFS 来写。

如果你更熟 BFS，也完全可以用 BFS 遍历连通块。

一句话总结

这题的本质是：

把城市看成图节点，省份数量就是连通分量数量。

  • 想先理解图连通性：用 DFS / BFS
  • 想练经典模板：用 并查集

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个 DFS 版本：

ts
function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length
    const visited = new Array(n).fill(false)

    const dfs = (city: number): void => {
        visited[city] = true

        for (let next = 0; next < n; next++) {
            if (isConnected[city][next] === 1 && !visited[next]) {
                dfs(next)
            }
        }
    }

    let provinces = 0
    for (let city = 0; city < n; city++) {
        if (!visited[city]) {
            provinces++
            dfs(city)
        }
    }

    return provinces
}

因为这个版本：

  • 最直观
  • 最容易和“连通块”概念对应起来
  • 是图遍历入门非常好的题