博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Luogu3388 割点模板
阅读量:5214 次
发布时间:2019-06-14

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

#include
#include
#include
using namespace std;int head[1000005],low[1000005],dfn[1000005],cut[1000005],n,m,cnt,time;struct edge{ int v,next;}e[1000005];inline void add(int u,int v){ e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt;}inline void tarjan(int u,int fa){ low[u]=dfn[u]=++time; int child=0; for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(!dfn[v]){ tarjan(v,fa); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]&&u!=fa)cut[u]=1; if(u==fa)child++; } low[u]=min(low[u],dfn[v]); } if(child>=2&&u==fa)cut[u]=1;}int main(){ memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); add(x,y);add(y,x); } for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i); int ans=0; for(int i=1;i<=n;i++){ if(cut[i])ans++; } printf("%d\n",ans); for(int i=1;i<=n;i++){ if(cut[i])printf("%d ",i); }}

转载于:https://www.cnblogs.com/Y15BeTa/p/11270552.html

你可能感兴趣的文章
1162字符串逆序
查看>>
【转】Ubuntu环境搭建svn服务器
查看>>
svn客户端清空账号信息的两种方法
查看>>
springboot添加servlet的两种方法
查看>>
java的Array和List相互转换
查看>>
win7安装IIS
查看>>
idea设置内存大小
查看>>
springboot热部署JRebel插件
查看>>
java获取当前项目路径System.getProperty("user.dir")
查看>>
idea关闭sonarLint自动扫描
查看>>
java的byte[]与String相互转换
查看>>
idea打开Run Dashboard
查看>>
java注解简单使用
查看>>
【转】Axure RP9.0.0.3661Team Edition激活码
查看>>
springboot集成mybatisplus小例子
查看>>
jqGrid设置单选
查看>>
mysql查看和修改最大连接数
查看>>
【转】查看电脑显卡型号及显卡性能
查看>>
windows安装reids
查看>>
bat启动OpenOffice4
查看>>