0547. Number of Provinces
=========================
题目信息
--------
:题号: 0547
:难度: Medium
:主题: 无向图、邻接矩阵、传递连接、连通分量
:原题: `LeetCode 0547 `_
:重点: 城市通过直接或间接关系属于同一省份、矩阵对称且对角线为 1、返回连通分量数量
题目重述
--------
有 ``n`` 个城市,方阵 ``isConnected`` 描述它们的直接连接关系。若 ``isConnected[i][j] = 1``,城市 ``i`` 与城市 ``j`` 直接相连;连接关系是无向的,并且每个城市与自身相连。
若两个城市可以通过一条由若干直接连接组成的路径互相到达,则它们属于同一个省份。返回所有城市形成的省份数量,也就是该无向图的连通分量数。
自建示例
--------
形成两个独立省份:
.. code-block:: text
输入:isConnected = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
输出:2
解释:城市 0、1 相互连接,城市 2、3 相互连接,两组之间没有路径。
所有城市彼此孤立:
.. code-block:: text
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3
解释:除自身之外没有任何直接或间接连接,因此每个城市单独构成一个省份。
从未访问城市开始 DFS
--------------------
每次找到一个未访问城市,就把它作为新省份的起点,并沿邻接矩阵访问所有直接或间接可达城市。一次 DFS 完成一个连通分量,随后继续寻找下一个未访问城市。
C++ 实现
--------
.. code-block:: cpp
class Solution {
void visit(const std::vector>& graph,
std::vector& visited, int city) {
visited[city] = true;
for (int next = 0; next < static_cast(graph.size()); ++next) {
if (graph[city][next] == 1 && !visited[next]) {
visit(graph, visited, next);
}
}
}
public:
int findCircleNum(std::vector>& isConnected) {
int n = static_cast(isConnected.size());
std::vector 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)``。