开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第21天,点击查看活动详情
【LetMeFly】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求图的连通分量
这道题其实挺裸的,就是让求一个图的连通分量。
题目中,已经给了图的邻接矩阵,我们直接对图开始搜索就好。
初始时,建立一个布尔类型的数组,数组长度为节点个数(
),初始值全为
然后使用一个整数类型的变量
来记录找到的联通分量的个数,初始值为
具体思路是:我们遍历这
个节点,一旦遍历到某个节点,就把与这个节点相联通的所有的节点遍历一遍,并把答案数量加一。
遍历过程中,一个节点不论是怎么怎么遍历到的,都需要把布尔数组中这个节点对应的布尔值标记为
(表示该点已遍历)
- 时间复杂度
。每个节点都会被遍历一次,这个节点与其他节点的所有“连接情况”也会被遍历一次 - 空间复杂度
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;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~ Tisfy:letmefly.blog.csdn.net/article/det…
今天的文章LeetCode 0547. 省份数量:图的连通分量分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/16353.html