给定一张n个点m条边的无向图,请找到一个点数最多的点集S,满足:
1.对于点集中任何一个点,它至少与d个点集中的点相邻。 2.仅保留点集中的点后,剩下的图连通。
【bzoj4296】【PA2015】【Mistrzostwa】【bfs+dfs】
发布日期:2021-11-16 15:38:49
浏览次数:3
分类:技术文章
本文共 1130 字,大约阅读时间需要 3 分钟。
Description
Input
第一行包含三个正整数n,m,d(2<=n<=200000,1<=m<=200000,1<=d<n),分别表示点数,边数以及度数限制。
接下来m行,每行包含两个正整数a,b(1<=a,b<=n,a不等于b),表示a点和b点之间有一条边。Output
若无解,输出NIE。
否则第一行输出一个正整数k,表示你找到的点数最多的点集S的点数。 第二行输出k个正整数,按升序依次输出点集中的点的编号,若有多组解,输出任意一组。Sample Input
4 4 2
1 2
2 3
3 4
4 2
1 2
2 3
3 4
4 2
Sample Output
3
2 3 4
2 3 4
题解:
把所有度数小于d的点都删掉,然后在剩下的图中找一个最大联通块即可。
bfs+dfs;
代码:
#include#include #include #define N 200010#define M 200010using namespace std;int point[N],next[M<<1],cnt,n,m,x,y,k,d[N],q[N],f[N],a[N],ans,s[N];struct use{int st,en;}e[M<<1];void add(int x,int y){ next[++cnt]=point[x];point[x]=cnt; e[cnt].st=x;e[cnt].en=y;d[x]++;}void dfs(int x){ f[x]=1; for (int i=point[x];i;i=next[i]) if (!f[e[i].en]){ s[++s[0]]=e[i].en; dfs(e[i].en); }}int main(){ scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=m;i++){ scanf("%d%d",&x,&y); add(x,y);add(y,x); } int h(0),t(0); for (int i=1;i<=n;i++) if (d[i] ans){ ans=s[0]; for (int j=1;j<=ans;j++) a[j]=s[j]; } } if (ans==0){cout<<"NIE"<
转载地址:https://blog.csdn.net/sunshinezff/article/details/51137635 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年03月02日 06时36分15秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
python中true什么意思_python中的bool是什么意思
2019-04-21
jacobian 矩阵意义_Jacobian矩阵和Hessian矩阵的作用是什么?
2019-04-21
c++ jna 数据类型_JNA 使用总结
2019-04-21
拉格朗日matlab编程例题,Matlab习题讲解.doc
2019-04-21
case是不是php语言关键字,PHP语言 switch 的一个注意点
2019-04-21
linux php mkdir失败,linux – mkdir错误:参数无效
2019-04-21
config.php渗透,phpMyAdmin 渗透利用总结
2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例
2019-04-21
mysql整体会滚_滚mysql
2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据
2019-04-21
mssql连接mysql数据库文件_在本地 怎么远程连接MSSQL数据库
2019-04-21
mssql 远程无法连接mysql_解决SQLServer远程连接失败的问题
2019-04-21
linux mysql c++编程_Linux下进行MYSQL的C++编程起步手记
2019-04-21
Maria数据库怎么复制到mysql_MySQL、MariaDB数据库的AB复制配置过程
2019-04-21