当前位置: 首页 > news >正文

【算法】连通块问题(C/C++)

目录

连通块问题

解决思路

步骤:

初始化:

DFS函数:

复杂度分析

 代码实现(C++)

题目链接:2060. 奶牛选美 - AcWing题库

解题思路:

AC代码: 

题目链接:687. 扫雷 - AcWing题库 

解题思路:

AC代码:

总结:


连通块问题

连通块问题(Connected Component Problem)是一个经典的图论问题,通常用来找出图中的所有连通分量。给定一个无向图,连通块问题的目标是确定图中有多少个连通分量(即有多少个互相连通的节点组成的集合)

解决思路

  1. 深度优先搜索(DFS)广度优先搜索(BFS)
    • 可以从任意未访问的节点出发,进行DFS或BFS,标记所有能够访问到的节点,代表这个连通分量。
    • 重复这个过程,直到所有节点都被访问为止。每次从新的未访问节点出发时,就代表发现了一个新的连通分量。
  2. 并查集(Union-Find)
    • 并查集是一种有效的解决连通性问题的数据结构。可以通过合并节点来动态地找到连通分量。

在这里,我将使用DFS的方式解决该问题,并以邻接表的形式来表示图。


步骤:

初始化:

创建一个访问数组visited[]来跟踪每个顶点是否被访问过。
初始化visited[]数组,将所有顶点标记为未访问。

DFS函数:

定义一个递归函数DFS(vertex),该函数从给定的顶点开始进行深度优先搜索。
在DFS函数中:
将当前顶点标记为已访问。
访问所有与当前顶点相邻的未访问的顶点,并递归调用DFS。
遍历所有顶点:

对于图中的每个未访问的顶点,调用DFS函数。
记录连通块:

每当DFS从一个新的未访问的顶点开始时,就表示找到了一个新的连通块。
输出结果:

可以打印出每个连通块中的顶点,或者计算连通块的数量。

复杂度分析

  • 时间复杂度O(n + m),其中 n 是节点数,m 是边数。每个节点和每条边都被遍历一次。
  • 空间复杂度O(n + m),用于存储图的邻接表和访问数组。

这种解决方案适用于中小规模的图,如果图的节点数非常大,可以考虑并查集来优化连通性问题。


 代码实现(C++)

#include <iostream>
#include <vector>
using namespace std;const int MAX_N = 1000;  // 假设最多1000个节点
vector<int> graph[MAX_N];  // 邻接表表示图
bool visited[MAX_N];       // 访问标记数组// 深度优先搜索(DFS)
void dfs(int node) {visited[node] = true;  // 标记当前节点已访问for (int neighbor : graph[node]) {  // 遍历所有邻居节点if (!visited[neighbor]) {dfs(neighbor);  // 如果邻居节点未访问,继续DFS}}
}int main() {int n, m;  // n为节点数,m为边数cin >> n >> m;// 读取图的边for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;graph[u].push_back(v);graph[v].push_back(u);  // 无向图,双向连接}int connected_components = 0;  // 记录连通块数目// 遍历所有节点for (int i = 1; i <= n; i++) {if (!visited[i]) {  // 如果节点i未被访问,说明发现了一个新的连通块dfs(i);  // 对该节点进行DFSconnected_components++;  // 连通块数加1}}cout << connected_components << endl;return 0;
}

题目链接:2060. 奶牛选美 - AcWing题库

听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。

不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。

牛皮可用一个 N×M 的字符矩阵来表示,如下所示:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中,X 表示斑点部分。

如果两个 X 在垂直或水平方向上相邻(对角相邻不算在内),则它们属于同一个斑点,由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色,将两个斑点合为一个。

在上面的例子中,他只需要给三个 .. 区域内涂色即可(新涂色区域用 ∗∗ 表示):

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定,为了使两个斑点合为一个,他需要涂色区域的最少数量。

输入格式

第一行包含两个整数 N 和 M。

接下来 N 行,每行包含一个长度为 M 的由 X 和 .. 构成的字符串,用来表示描述牛皮图案的字符矩阵。

输出格式

输出需要涂色区域的最少数量。

数据范围

1≤N,M≤50

输入样例:

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

输出样例:

3

解题思路:

此题主要是运用dfs或者bfs去找连通块最小距离。搜索思想,先去找X的点,只要找到了一个X点,那么此点所在的连通块就一网打尽了,把此连通块的点存起来,再搜第二个连通块,把第二个连通块的点也都存起来,然后外循环第一个连通块的点,内循环第二个连通块的点,每次尝试两个点染色,就是图中第一个连通块黄色格子跟第二个连通块黄色格子求距离。在所有里面找一个min的值即可,途中红色的为最小。最后输出减一就是答案,因为这里求的是两点之间点的距离。


AC代码: 

#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<climits>
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
char s[N][N];//存图
vector<PII> points[2];//连通块
int dx[]={0,0,1,-1};//方向数组
int dy[]={1,-1,0,0};
int n,m;
int res=INT_MAX;//无穷大
void dfs(int a,int b,vector<PII>&p){s[a][b]='.';//走过此连通块的就置为'.'防止重复搜索p.push_back({a,b});//连通块所有的坐标for(int i=0;i<4;i++){int x=a+dx[i];int y=b+dy[i];if(x>=0&&y>=0&&x<n&&y<m&&s[x][y]=='X'){//符合条件就继续搜dfs(x,y,p);}}
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){cin>>s[i];}int k=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i][j]=='X'){//找到一个X就能找到此联通块dfs(i,j,points[k++]);}}}for(auto i:points[0]){//c++11遍历更简单for(auto j:points[1]){res=min(res,abs(i.first-j.first)+abs(i.second-j.second));//两个坐标差值}}//最后要减一,比如(1,1)与(1,3)之间只有一个(1,2),做差为2,所以要减一cout<<res-1<<endl;return 0;
}

题目链接:687. 扫雷 - AcWing题库 

扫雷是一种计算机游戏,在 2020 世纪 8080 年代开始流行,并且仍然包含在某些版本的 Microsoft Windows 操作系统中。

在这个问题中,你正在一个矩形网格上玩扫雷游戏。

最初网格内的所有单元格都呈未打开状态。

其中 M 个不同的单元格中隐藏着 M 个地雷。

其他单元格内不包含地雷。

你可以单击任何单元格将其打开。

如果你点击到的单元格中包含一个地雷,那么游戏就会判定失败。

如果你点击到的单元格内不含地雷,则单元格内将显示一个 0 到 8 之间的数字(包括 0 和 8),这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。

如果两个单元格共享一个角或边,则它们是相邻单元格。

另外,如果某个单元格被打开时显示数字 0,那么它的所有相邻单元格也会以递归方式自动打开。

当所有不含地雷的单元格都被打开时,游戏就会判定胜利。

例如,网格的初始状态可能如下所示(* 表示地雷,而 c 表示第一个点击的单元格):

*..*...**.
....*.....
..c..*....
........*.
..........

被点击的单元格旁边没有地雷,因此当它被打开时显示数字 0,并且它的 8 个相邻单元也被自动打开,此过程不断继续,最终状态如下:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时,仍有不包含地雷的单元格(用 . 字符表示)未被打开,因此玩家必须继续点击未打开的单元格,使游戏继续进行。

你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。

给定网格的尺寸(N×N),输出能够获胜的最小点击次数。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据第一行包含整数 N,表示游戏网格的尺寸大小。

接下来 N 行,每行包含一个长度为 N 的字符串,字符串由 .(无雷)和 *(有雷)构成,表示游戏网格的初始状态。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为 Case #x: y,其中 x 是组别编号(从 1 开始),y 是获胜所需的最小点击次数。

数据范围

1≤T≤100
1≤N≤300

输入样例:

2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...

输出样例:

Case #1: 2
Case #2: 8

解题思路:

此题是DFS求连通块,扫雷中分三种情况,如果你点一次,此点附近没有雷,那么这一个0连通块就会全部显示出来,此0连通块边界就会显示此点附近雷的个数。第二种就是不在0连通块,附近有雷的点,为了要赢,这个也必须要点。第三种就是在连通块里面,附近有雷的点,这个点对于此题来说,先点了第一种,那么第三种的点也被包含在里面了,省了一步,此题要求最少点多少次,那么答案就是0连通块的数量+不在0连通块,附近有雷的点(1--8)。此题可用DFS、BFS进行找0联通块。

视频讲解:AcWing 687. 扫雷(每日一题)_哔哩哔哩_bilibili

AC代码:

#include<iostream>
using namespace std;
const int N=305;
int n,T;
char str[N][N];
int a[N][N];//标记(i,j)点附近有几个雷
void dfs(int x,int y){int t=a[x][y];a[x][y]=-1;if(t){return;}for(int i=x-1;i<=x+1;i++){for(int j=y-1;j<=y+1;j++){if(i>=0&&j>=0&&i<n&&j<n&&a[i][j]!=-1){dfs(i,j);}}}
}
int main(){cin>>T;for(int k=1;k<=T;k++){cin>>n;for(int j=0;j<n;j++){cin>>str[j];}int res=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(str[i][j]=='*'){//如果此点是雷标记为-1a[i][j]=-1;}else{a[i][j]=0;for(int l=i-1;l<=i+1;l++){for(int r=j-1;r<=j+1;r++){if(str[l][r]=='*'&&l>=0&&r>=0&&l<n&&r<n){//附近是雷且没有越界a[i][j]++;}}}}}}for(int i=0;i<n;i++){//求为0的连通块for(int j=0;j<n;j++){if(a[i][j]==0){res++;dfs(i,j);}}}for(int i=0;i<n;i++){//求不属于0连通块且不是雷的点for(int j=0;j<n;j++){if(a[i][j]!=-1){res++;}}}cout<<"Case #"<<k<<":"<<res<<endl;}return 0;
}

总结:

此题思路难想,当思路打开了,按照板子就可以写出来,需要多练习问题转化能力,如此题转化为连通块最小距离。用dfs或者bfs进行图的遍历,寻找有用的信息。文章若有错误、不足的地方恳请大家指出,一起加油。

执笔至此,感触彼多,全文降至、落笔为终,感谢大家的支持。

相关文章:

【算法】连通块问题(C/C++)

目录 连通块问题 解决思路 步骤&#xff1a; 初始化&#xff1a; DFS函数&#xff1a; 复杂度分析 代码实现&#xff08;C&#xff09; 题目链接&#xff1a;2060. 奶牛选美 - AcWing题库 解题思路&#xff1a; AC代码&#xff1a; 题目链接&#xff1a;687. 扫雷 -…...

如何选择黑白相机和彩色相机

我们在选择成像解决方案时黑白相机很容易被忽略&#xff0c;因为许多新相机提供鲜艳的颜色&#xff0c;鲜明的对比度和改进的弱光性能。然而&#xff0c;有许多应用&#xff0c;选择黑白相机将是更好的选择&#xff0c;因为他们产生更清晰的图像&#xff0c;更好的分辨率&#…...

Rust 力扣 - 740. 删除并获得点数

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 首先对于这题我们如果将所有点数装入一个切片f中&#xff0c;该切片f中的i号下标表示所有点数为i的点数之和 那么这题就转换成了打家劫舍这道题&#xff0c;也就是求选择了切片中某个下标的元素后&#xff0c;该…...

OpenCV从入门到精通实战(七)——探索图像处理:自定义滤波与OpenCV卷积核

本文主要介绍如何使用Python和OpenCV库通过卷积操作来应用不同的图像滤波效果。主要分为几个步骤&#xff1a;图像的读取与处理、自定义卷积函数的实现、不同卷积核的应用&#xff0c;以及结果的展示。 卷积 在图像处理中&#xff0c;卷积是一种重要的操作&#xff0c;它通过…...

Docker核心概念总结

本文只是对 Docker 的概念做了较为详细的介绍&#xff0c;并不涉及一些像 Docker 环境的安装以及 Docker 的一些常见操作和命令。 容器介绍 Docker 是世界领先的软件容器平台&#xff0c;所以想要搞懂 Docker 的概念我们必须先从容器开始说起。 什么是容器? 先来看看容器较为…...

环形缓冲区

什么是环形缓冲区 环形缓冲区,也称为循环缓冲区或环形队列,是一种特殊的FIFO(先进先出)数据结构。它使用一块固定大小的内存空间来缓存数据,并通过两个指针(读指针和写指针)来管理数据的读写。当任意一个指针到达缓冲区末尾时,会自动回绕到缓冲区开头,形成一个"环"。…...

jQuery-Word-Export 使用记录及完整修正文件下载 jquery.wordexport.js

参考资料&#xff1a; jQuery-Word-Export导出word_jquery.wordexport.js下载-CSDN博客 近期又需要自己做个 Html2Doc 的解决方案&#xff0c;因为客户又不想要 Html2pdf 的下载了&#xff0c;当初还给我费尽心思解决Html转pdf时中文输出的问题&#xff08;html转pdf文件下载之…...

云服务器部署WebSocket项目

WebSocket是一种在单个TCP连接上进行全双工通信的协议&#xff0c;其设计的目的是在Web浏览器和Web服务器之间进行实时通信&#xff08;实时Web&#xff09; WebSocket协议的优点包括&#xff1a; 1. 更高效的网络利用率&#xff1a;与HTTP相比&#xff0c;WebSocket的握手只…...

C#+数据库 实现动态权限设置

将权限信息存储在数据库中&#xff0c;支持动态调整。根据用户所属的角色、特定的功能模块&#xff0c;动态加载权限” 1. 数据库设计 根据这种需求&#xff0c;可以通过以下表设计&#xff1a; 用户表 (Users)&#xff1a;存储用户信息。角色表 (Roles)&#xff1a;存储角色…...

(原创)Android Studio新老界面UI切换及老版本下载地址

前言 这两天下载了一个新版的Android Studio&#xff0c;发现整个界面都发生了很大改动&#xff1a; 新的界面的一些设置可参考一些博客&#xff1a; Android Studio新版UI常用设置 但是对于一些急着开发的小伙伴来说&#xff0c;没有时间去适应&#xff0c;那么怎么办呢&am…...

Ubuntu24虚拟机-gnome-boxes

推荐使用gnome-boxes&#xff0c; virtualbox构建失败&#xff0c;multipass需要开启防火墙 sudo apt install gnome-boxes创建完毕&#xff5e;...

k8s rainbond centos7/win10 -20241124

参考 https://www.rainbond.com/ 国内一站式云原生平台 对centos7环境支持不太行 [lighthouseVM-16-5-centos ~]$ curl -o install.sh https://get.rainbond.com && bash ./install.sh 2024-11-24 09:56:57 ERROR: Ops! Docker daemon is not running. Start docke…...

SpringBoot+Vue滑雪社区网站设计与实现

【1】系统介绍 研究背景 随着互联网技术的快速发展和冰雪运动的普及&#xff0c;滑雪作为一种受欢迎的冬季运动项目&#xff0c;吸引了越来越多的爱好者。与此同时&#xff0c;社交媒体和在线社区平台的兴起为滑雪爱好者提供了一个交流经验、分享心得、获取信息的重要渠道。滑…...

MySql.2

sql查询语句执行过程 SQL 查询语句的执行过程是一个复杂的过程&#xff0c;涉及多个步骤。以下是典型的关系数据库管理系统 (RDBMS) 中 SQL 查询语句的执行过程概述&#xff1a; 1. ‌客户端发送查询‌ 用户通过 SQL 客户端或应用程序发送 SQL 查询语句给数据库服务器。 2. ‌…...

算法之区间和题目讲解

题干 难度&#xff1a;简单 题目分析 题目要求算出每个指定区间内元素的总和。 然而&#xff0c;区间在输入的最下面&#xff0c;所以按照暴力破解的思路&#xff0c;我们首先要遍历数组&#xff0c;把它的值都存进去。 然后&#xff0c;遍历下面的区间&#xff0c;从索引a…...

价格分类(神经网络)

# 1.导入依赖包 import timeimport torch import torch.nn as nn import torch.optim as optimfrom torch.utils.data import TensorDataset, DataLoader from sklearn.model_selection import train_test_splitimport numpy as np import pandas as pd import matplotlib.pypl…...

对智能电视直播App的恶意监控

首先我们要指出中国广电总局推出的一个政策性文件是恶意监控的始作俑者&#xff0c;这个广电总局的政策性文件禁止智能电视和电视盒子安装直播软件。应该说这个政策性文件是为了保护特殊利益集团&#xff0c;阻挠技术进步和发展的。 有那么一些电视机和电视盒子的厂商和电信运…...

【JavaEE初阶】多线程初阶下部

文章目录 前言一、volatile关键字volatile 能保证内存可见性 二、wait 和 notify2.1 wait()方法2.2 notify()方法2.3 notifyAll()方法2.4 wait 和 sleep 的对比&#xff08;面试题&#xff09; 三、多线程案例单例模式 四、总结-保证线程安全的思路五、对比线程和进程总结 前言…...

macOS上进行Ant Design Pro实战教程(一)

由于一个AI项目的前端使用了umi&#xff0c;本教程根据阿里官网上的 《Ant Design 实战教程&#xff08;beta 版&#xff09;》来实操一下&#xff0c;我使用macOS操作系统&#xff0c;VS Code 开发环境。 一、开发环境 1、安装nodejs, npm, yarn 官网上建议使用cnpm&#xf…...

智能合约运行原理

点个关注吧&#xff01;&#xff01; 用一句话来总结&#xff0c;智能合约就像是一个自动售货机&#xff1a;你投入硬币&#xff08;触发条件&#xff09;&#xff0c;选择商品&#xff08;执行合约&#xff09;&#xff0c;然后机器就会自动给你商品&#xff08;执行结果&…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...