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题解省份数量的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C C++ 题解LeetCode2360图中的最长环示例

    C C++ 题解LeetCode2360图中的最长环示例

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:2360. 图中的最长环 给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边. 图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 . 请你返回图中的 最长 环,如果没有任何环,请返回 -1 . 一个环指的是起点和终点是 同一个 

  • Java C++题解leetcode902最大为N的数字组合数位DP

    目录 题目要求 阅读理解 思路:数位DP Java C++ 总结 题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int[digits.length]; for (int i = 0; i < digits.length; i++) nums[i] = Integer.parseIn

  • C C++ 题解LeetCode1417重新格式化字符串

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1417. 重新格式化字符串 给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母. 请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同.也就是说,字母后面应该跟着数字,而数字后面应该跟着字母. 请你返回 重新格式化后 的字符串:如果无法按要求重新格式化,则返回一个 空字符串 . 提示: 1⩽s.length⩽5001 s 仅由小写英文字母和/或数字组成. 示例 1: 输入:s

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • 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

  • python爬取全国火锅店数量并可视化展示

    python爬取全国火锅店数量并可视化展示

    目录 一.网页分析 二.获取数据 1.导入相关库 2.请求数据 3.保存到excel 三.数据可视化 1.全国火锅店数量分布 2.四川火锅店数量分布 四.小结 前言: 今天教大家如何获取全国不同城市火锅店数量情况,并将这些数据进行可视化展示,以更加直观的方式去浏览全国不同省份.不同城市的火锅店分布情况. 本文数据来自于某度地图,通过python技术知识去获取数据并进行可视化. 一.网页分析 首先先看一下数据源,在某度地图里面按照下方操作,就可以请求到全国的火锅店情况(从下图来看没有显示出来,但是

  • Python算法之图的遍历

    Python算法之图的遍历

    本节主要介绍图的遍历算法BFS和DFS,以及寻找图的(强)连通分量的算法 Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点.对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit).遍历的重要性自然不必说,图中有几个算法和遍历没有关系?! [算法导论对于发现和访问区别的非常明显,对图的算法讲解地特别好,在遍历节点的时候给节点标注它的发现节点时间d[v]和结束访问时间f[v],然后由这些时间的一些规律得到了不少实用的定理,本节后面介绍了部分内容,感

  • java并查集算法带你领略热血江湖

    java并查集算法带你领略热血江湖

    目录 一.什么是并查集 二.深入理解并查集 三.实现并查集 四.真题训练 五.路径压缩优化 六.总结 你好,我是小黄,一名独角兽企业的Java开发工程师. 校招收获数十个offer,年薪均20W~40W. 感谢茫茫人海中我们能够相遇, 俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习, 希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想. 一.什么是并查集 并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于处理一些不相交集合的合并问题,并支持两种操作: 合并

  • go语言题解LeetCode1128等价多米诺骨牌对的数量

    目录 题目描述 思路分析 AC 代码 偷懒解法 思路: 图解: 代码: 哈希表+元素转换 解题思路 代码 复杂度分析 题目描述 1128. 等价多米诺骨牌对的数量 - 力扣(LeetCode) 给你一个由一些多米诺骨牌组成的列表 dominoes. 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的. 形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d,或是 

  • 算法系列15天速成 第十四天 图【上】

    算法系列15天速成 第十四天 图【上】

    今天来分享一下图,这是一种比较复杂的非线性数据结构,之所以复杂是因为他们的数据元素之间的关系是任意的,而不像树那样 被几个性质定理框住了,元素之间的关系还是比较明显的,图的使用范围很广的,比如网络爬虫,求最短路径等等,不过大家也不要胆怯, 越是复杂的东西越能体现我们码农的核心竞争力. 既然要学习图,得要遵守一下图的游戏规则. 一: 概念 图是由"顶点"的集合和"边"的集合组成.记作:G=(V,E): <1> 无向图 就是"图"中的边没

  • Java编程实现深度优先遍历与连通分量代码示例

    Java编程实现深度优先遍历与连通分量代码示例

    深度优先遍历 深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达. 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点. 当回退到的路口已没有可走的通道时继续回退. 而连通分量,看概念:无向图G的极大连通子图称为G的连通分量( Connected Component).任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量. 下面看看具体实例: package com.dataStructure.gra

  • Python Pyecharts绘制象形柱图

    Python Pyecharts绘制象形柱图

    目录 1.准备工作 1.1 导入模块 1.2 部分参数 2.基础象形图 3.自定义图例 3.1 图片图例 3.2 生成象形图 在可视化展示过程中,为了达到更形象的展示效果,我们往往需要自定义一些直观的图例,本期给大家介绍可视化库Pyecharts中的象形柱图,希望对你有所帮助. 1.准备工作 1.1 导入模块 from pyecharts import options as opts from pyecharts.charts import PictorialBar from pyecharts

  • C++处理图存储的方式分享

    C++处理图存储的方式分享

    目录 一.邻接矩阵 二.邻接表 三.链式前向星 1.AcWing方式(纯数组) 三.Acwing图的存储方式 2.复杂度 2.应用 3.邻接表 4.代码实现 5.插入边 四.遍历 1.深度优先遍历 2.广度优先遍历 3.复杂度 4.应用 5.实现案例 6. 结构体+数组 7. 结构体+数组(2) 一.邻接矩阵 适用: 稠密图,就是说点数的平方与边数接近的情况,换句话说就是边特别多. 不适用: 稀疏图,就是点数的平方与边数差的特别多,边数少,但点数多,就不行了,因为空间占用太大了. 实现代码: #

随机推荐