LeetCode 0547. 省份数量:图的连通分量

LeetCode 0547. 省份数量:图的连通分量开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第21天,点击查看活动详情 【LetMeFly】547.省份数量 力扣题目链接:https://leetcode.cn/proble

开启掘金成长之旅!这是我参与「掘金日新计划 · 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:

LeetCode 0547. 省份数量:图的连通分量

输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出:2

示例 2:

LeetCode 0547. 省份数量:图的连通分量

输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出:3

 

提示:

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j]10
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

方法一:BFS求图的连通分量

这道题其实挺裸的,就是让求一个图的连通分量。

题目中,已经给了图的邻接矩阵,我们直接对图开始搜索就好。

初始时,建立一个布尔类型的数组,数组长度为节点个数(
l e n ( i s C o n n e c t e d ) len(isConnected)
),初始值全为
f a l s e false

然后使用一个整数类型的变量
a n s ans
来记录找到的联通分量的个数,初始值为
0 0

具体思路是:我们遍历这
n n
个节点,一旦遍历到某个节点,就把与这个节点相联通的所有的节点遍历一遍,并把答案数量加一。

遍历过程中,一个节点不论是怎么怎么遍历到的,都需要把布尔数组中这个节点对应的布尔值标记为
t r u e true
(表示该点已遍历)

  • 时间复杂度
    O ( l e n ( i s C o n n e c t e d ) 2 ) O(len(isConnected)^2)
    。每个节点都会被遍历一次,这个节点与其他节点的所有“连接情况”也会被遍历一次
  • 空间复杂度
    O ( l e n ( i s C o n n e c t e d ) ) 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;
    }
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~ Tisfy:letmefly.blog.csdn.net/article/det…

今天的文章LeetCode 0547. 省份数量:图的连通分量分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/16353.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注