C++ LeetCode0547题解省份数量图的连通分量
目录
- LeetCode 547.省份数量
- 方法一:BFS求图的连通分量
- AC代码
- C++
LeetCode 547.省份数量
力扣题目链接:leetcode.cn/problems/nu…
有 n
个城市,其中一些彼此相连,另一些没有相连。如果城市 a
与城市 b
直接相连,且城市 b
与城市 c
直接相连,那么城市 a
与城市 c
间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n
的矩阵 isConnected
,其中 isConnected[i][j] = 1
表示第 i
个城市和第 j
个城市直接相连,而 isConnected[i][j] = 0
表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1:
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2
示例 2:
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3
提示:
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j]
为1
或0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
方法一:BFS求图的连通分量
这道题其实挺裸的,就是让求一个图的连通分量。
题目中,已经给了图的邻接矩阵,我们直接对图开始搜索就好。
初始时,建立一个布尔类型的数组,数组长度为节点个数(len(isConnected)len(isConnected)len(isConnected)),初始值全为falsefalsefalse
然后使用一个整数类型的变量ansansans来记录找到的联通分量的个数,初始值为000
具体思路是:我们遍历这nnn个节点,一旦遍历到某个节点,就把与这个节点相联通的所有的节点遍历一遍,并把答案数量加一。
遍历过程中,一个节点不论是怎么怎么遍历到的,都需要把布尔数组中这个节点对应的布尔值标记为truetruetrue(表示该点已遍历)
- 时间复杂度O(len(isConnected)2)O(len(isConnected)^2)O(len(isConnected)2)。每个节点都会被遍历一次,这个节点与其他节点的所有“连接情况”也会被遍历一次
- 空间复杂度O(len(isConnected))O(len(isConnected))O(len(isConnected))
AC代码
C++
class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int n = isConnected.size(); vector<bool> visited(n, false); int ans = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { visited[i] = true; queue<int> q; q.push(i); ans++; while (q.size()) { int thisNode = q.front(); q.pop(); for (int to = 0; to < n; to++) { if (isConnected[thisNode][to] && !visited[to]) { visited[to] = true; q.push(to); } } } } } return ans; } };
以上就是C++ LeetCode0547题解省份数量图的连通分量的详细内容,更多关于C++ LeetCode题解省份数量的资料请关注我们其它相关文章!