跳过并跳转到主要内容
BigO

输入内容开始搜索…

↑↓进行选择
Esc

省份数量

给定一个 $n \times n$ 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示城市 $i$ 和城市 $j$ 直接相连，为 $0$ 则不直接相连。如果城市 $a$ 与 $b$ 相连，$b$ 与 $c$ 相连，则 $a$ 与 $c$ 间接相连，这些相互直接或间接相连的城市共同组成一个“省份”。你需要返回矩阵中省份（独立的连通城市区域）的总数量。

LeetCode2分钟阅读

题目核心是求无向图中的连通分量个数。每个城市看作图中的一个节点，如果两个城市相连（isConnected[i][j] == 1），则它们属于同一个连通分量（省份）。

常见的解题思路有以下三种：

图中的每个城市可以看作一个节点，若 isConnected[i][j] == 1，则表示城市 i 和城市 j 之间存在一条无向边。DFS 的核心在于“顺藤摸瓜”，尽量深地搜索图的分支。

  1. 维护访问状态：
    • 维护一个布尔数组 visited（大小为 nn），记录每个城市是否已经被访问过，防止重复计算和陷入死循环。
  2. 遍历所有节点：
    • 依次遍历每一个城市 ii（0≤i<n0 \le i < n）。
    • 如果城市 ii 未被访问过，说明它属于一个新的省份：
      • 将省份计数器 count 加 1。
      • 以城市 ii 为起点发起一次 DFS 递归搜索，将与城市 ii 直接或间接相连的所有城市都在 visited 中标记为 true（即把这整块连通区域一次性吃透）。
  3. 递归搜索（DFS 过程）：
    • 在对城市 ii 进行 DFS 时，遍历所有可能的城市 jj。
    • 若 isConnected[i][j] == 1（二者相连）且 visited[j] 为 false（jj 未被访问）：
      • 将 jj 标记为已访问 visited[j] = true。
      • 递归调用 DFS，继续搜索以 jj 为起点相连的其他城市。
  4. 返回结果：
    • 主循环遍历完成后，所有的连通块都被识别出来，此时 count 的值即为省份数量。

#include <vector>
using namespace std;


class Solution {
private:
    // DFS 辅助函数，递归标记与当前城市相连的所有城市
    void dfs(const vector<vector<int>>& isConnected, vector<bool>& visited, int i) {
        // 将当前城市标记为已访问
        visited[i] = true;


        // 遍历所有可能的城市 j
        for (int j = 0; j < isConnected.size(); ++j) {
            // 如果城市 i 和城市 j 相连，且城市 j 尚未访问过，则继续递归 DFS
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }


public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false); // 记录每个城市是否被访问
        int provinceCount = 0;           // 省份数量计数器


        // 遍历每一个城市
        for (int i = 0; i < n; ++i) {
            // 如果城市 i 还没被访问过，说明找到了一个新的省份
            if (!visited[i]) {
                provinceCount++;
                dfs(isConnected, visited, i); // DFS 标记出该省份包含的所有城市
            }
        }


        return provinceCount;
    }
};

  • 时间复杂度：O(n2)O(n^2)，其中 nn 是城市的数量。我们需要遍历每个节点一次，而在 DFS 内部，对于每个节点都需要检查它与其他 nn 个节点是否有边连接，因此总时间复杂度为 O(n2)O(n^2)。
  • 空间复杂度：O(n)O(n)，主要是 visited 数组的大小为 nn，以及递归调用栈的最大深度最坏情况下为 nn（图退化为一条链时）。

BFS 的思路可以类比为“水滴涟漪”：从一个未访问的城市（起点）开始，先将其标记并放入队列，然后不断从队列中取出城市，将其所有直接相连的未访问城市都加入队列，直到该省份内的所有城市都被连带遍历完毕。

  1. 状态维护：
    • 布尔数组 visited（大小为 nn）：记录城市是否已被搜索过。
    • 队列 queue：用于暂存待处理的城市节点。
  2. 主流程遍历：
    • 依次遍历每个城市 ii（0≤i<n0 \le i < n）。
    • 如果城市 ii 未被访问过：
      • 说明找到了一个新的连通块（省份），省份计数 count 加 1。
      • 将 ii 标记为已访问 visited[i] = true，并将 ii 入队，开始 BFS 拓展。
  3. 队列拓展（BFS 过程）：
    • 当队列不为空时，弹出队头城市 currcurr。
    • 遍历所有可能与 currcurr 相连的城市 jj。
    • 若 isConnected[curr][j] == 1 且 visited[j] 为 false：
      • 将城市 jj 标记为已访问 visited[j] = true（注意：入队时立即标记，防止重复入队）。
      • 将城市 jj 压入队列。
    • 重复上述过程，直到队列清空，表示当前省份的所有城市已全部找到。
  4. 返回结果：
    • 遍历完所有城市后，返回累加的省份数量。

#include <vector>
#include <queue>
using namespace std;


class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false); // 记录城市是否被访问
        int provinceCount = 0;           // 省份数量
        queue<int> q;                    // BFS 队列


        for (int i = 0; i < n; ++i) {
            // 发现未访问的城市，说明存在一个新的省份
            if (!visited[i]) {
                provinceCount++;
                visited[i] = true;
                q.push(i); // 将起点放入队列


                // 开始 BFS 遍历当前省份包含的所有城市
                while (!q.empty()) {
                    int curr = q.front();
                    q.pop();


                    for (int j = 0; j < n; ++j) {
                        // 如果 curr 和 j 相连，且 j 尚未访问
                        if (isConnected[curr][j] == 1 && !visited[j]) {
                            visited[j] = true; // 标记已访问
                            q.push(j);         // 入队继续拓展
                        }
                    }
                }
            }
        }


        return provinceCount;
    }
};

  • 时间复杂度：O(n2)O(n^2)，其中 nn 为城市数量。图中的每个节点最多入队和出队一次，处理每个节点时都需要扫描长度为 nn 的整行邻接矩阵。
  • 空间复杂度：O(n)O(n)，主要由 visited 数组和辅助队列 q 产生，队列中最多同时保存 nn 个节点。

在这道题中，矩阵 isConnected 中的每个城市代表一个节点。并查集的核心思想是通过“合并”与“查找”操作，把所有连通的城市放到同一个集合（省份）中。

  1. 初始化：
    • 假设有 nn 个城市，初始时每个城市各自独立，为一个单独的集合。
    • 建立父节点数组 parent，初始时 parent[i] = i，表示每个节点的根节点就是自己。
    • 初始化省份总数为 nn。
  2. 合并集合（Union）：
    • 遍历邻接矩阵 isConnected 的上三角部分（因为矩阵关于对角线对称）。
    • 若 isConnected[i][j] == 1，说明城市 ii 和 jj 相连。
    • 分别寻找 ii 和 jj 的根节点：
      • 如果两者的根节点不同，说明它们原本属于不同省份，此时将两个集合合并（例如将 jj 的根节点指向 ii 的根节点），并将总省份数 减 1。
      • 如果根节点相同，说明它们已经在同一个省份中，无需操作。
  3. 查找根节点（Find + 路径压缩）：
    • 顺着 parent 数组向上寻找节点的最终根节点。
    • 为了防止树退化成链表，在查找过程中顺便进行路径压缩（即在递归寻找根节点时，将当前节点直接指向根节点），将查找的时间复杂度降至近乎 O(1)O(1)。
  4. 返回结果：
    • 遍历完所有边后，最终剩余的独立集合数量即为省份数量。

#include <vector>
using namespace std;


class UnionFind {
private:
    vector<int> parent; // 记录每个节点的父节点
    int count;          // 记录连通分量（省份）的数量


public:
    // 初始化并查集
    UnionFind(int n) {
        count = n;
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 初始时每个节点的根节点是自身
        }
    }


    // 查找节点 x 的根节点（带路径压缩）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩，直接指向根节点
        }
        return parent[x];
    }


    // 合并节点 x 和节点 y 所在的集合
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);


        /*
         * 说明：为什么 rootX == rootY 时不需要 count-- ？
         * 1. count 维护的是独立集合（连通分量）的总数，初始为 n。
         * 2. 当 rootX != rootY 时：说明 x 和 y 属于两个不同的集合，合并它们会让总集合数减少 1，因此 count--。
         * 3. 当 rootX == rootY 时：说明 x 和 y 在此之前已经直接或间接相连（在同一个集合内）。
         *    此时再加一条边只是在集合内部连线（形成环），并没有融合新的独立集合，因此集合总数不变，无需 count--。
         */
        if (rootX != rootY) {
            parent[rootY] = rootX; // 将 rootY 的父节点设为 rootX
            count--;               // 成功合并两个不同的集合，省份数量减 1
        }
    }


    // 获取当前连通分量数量
    int getCount() {
        return count;
    }
};


class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        UnionFind uf(n);


        // 遍历矩阵上三角部分，合并有边连接的节点
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (isConnected[i][j] == 1) {
                    uf.unite(i, j);
                }
            }
        }


        return uf.getCount();
    }
};

  • 时间复杂度：O(n2⋅α(n))O(n^2 \cdot \alpha(n))，其中 nn 为城市数量，α\alpha 是反阿克曼函数（增长极其缓慢，通常可看作常数 O(1)O(1)）。我们需要遍历对称矩阵的半边 O(n2)O(n^2)，每次合并和查找耗时接近 O(1)O(1)。
  • 空间复杂度：O(n)O(n)，主要是存储节点父节点信息的 parent 数组占用的空间。

方法实现难度适用场景
DFS简单（最推荐）代码量最少，适合面试快速书写
BFS简单迭代实现，避免递归过深导致的栈溢出
并查集中等适合处理动态连通性问题或大规模图结构

© 2026 三七开 · 一方通行，只管向前。

旅途由 Astro 驱动 · 主题 Chirping Astro