【bzoj4296】【PA2015】【Mistrzostwa】【bfs+dfs】
发布日期:2021-11-16 15:38:49 浏览次数:3 分类:技术文章

本文共 1130 字,大约阅读时间需要 3 分钟。

Description

给定一张n个点m条边的无向图,请找到一个点数最多的点集S,满足:

1.对于点集中任何一个点,它至少与d个点集中的点相邻。
2.仅保留点集中的点后,剩下的图连通。

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

Sample Output

3
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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj4500】【矩阵】【dfs】
下一篇:【bzoj3119】【book】【贪心】

发表评论

最新留言

逛到本站,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
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21
php foreach 数据库,php – 使用foreach将数据库检索的数据排列在HTML表中 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
java list 合并 重复的数据_Java ArrayList合并并删除重复数据3种方法 2019-04-21
android volley 上传图片 和参数,android - 使用android中的volley将图像上传到multipart中的服务器 - 堆栈内存溢出... 2019-04-21
android开发的取消清空按钮,Android开发实现带清空按钮的EditText示例 2019-04-21
android gp服务,ArcGIS Runtime SDK for Android开发之调用GP服务(异步调用) 2019-04-21
mysql整体会滚_滚mysql 2019-04-21
向mysql数据库中添加批量数据类型_使用JDBC在MySQL数据库中快速批量插入数据 2019-04-21
最全的mysql 5.7.13_最全的mysql 5.7.13 安装配置方法图文教程(linux) 强烈推荐! 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