0547. Number of Provinces

题目信息

题号:

0547

难度:

Medium

主题:

无向图、邻接矩阵、传递连接、连通分量

原题:

LeetCode 0547

重点:

城市通过直接或间接关系属于同一省份、矩阵对称且对角线为 1、返回连通分量数量

题目重述

有 n 个城市,方阵 isConnected 描述它们的直接连接关系。若 isConnected[i][j] = 1,城市 i 与城市 j 直接相连;连接关系是无向的,并且每个城市与自身相连。

若两个城市可以通过一条由若干直接连接组成的路径互相到达,则它们属于同一个省份。返回所有城市形成的省份数量,也就是该无向图的连通分量数。

自建示例

形成两个独立省份:

输入:isConnected = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
输出:2
解释:城市 0、1 相互连接,城市 2、3 相互连接,两组之间没有路径。

所有城市彼此孤立:

输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3
解释:除自身之外没有任何直接或间接连接,因此每个城市单独构成一个省份。

从未访问城市开始 DFS

每次找到一个未访问城市,就把它作为新省份的起点,并沿邻接矩阵访问所有直接或间接可达城市。一次 DFS 完成一个连通分量,随后继续寻找下一个未访问城市。

C++ 实现

class Solution {
    void visit(const std::vector<std::vector<int>>& graph,
               std::vector<bool>& visited, int city) {
        visited[city] = true;
        for (int next = 0; next < static_cast<int>(graph.size()); ++next) {
            if (graph[city][next] == 1 && !visited[next]) {
                visit(graph, visited, next);
            }
        }
    }

public:
    int findCircleNum(std::vector<std::vector<int>>& isConnected) {
        int n = static_cast<int>(isConnected.size());
        std::vector<bool> visited(n, false);
        int provinces = 0;
        for (int city = 0; city < n; ++city) {
            if (visited[city]) continue;
            ++provinces;
            visit(isConnected, visited, city);
        }
        return provinces;
    }
};

代码分析

访问标记保证每座城市只被归入一个连通分量;无向矩阵中的路径可通过递归传递,因此一次 DFS 恰好覆盖一个省份。遍历矩阵时间复杂度为 O(n^2),访问标记和递归栈空间为 O(n)。