大夏网,雄霸蛮荒燃文,亚欧水貂
目录
tarjan求割点
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #define min_(a,b) a>b?b:a; #define maxn 100010 int n,m,cnt,id; int head[maxn]; int dfn[maxn],low[maxn]; bool cut[maxn]; struct edge{ int next,to; }edge[200001];//无向图 inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } void add_edge(int from,int to){ edge[++cnt].to=to,edge[cnt].next=head[from],head[from]=cnt; } void tarjan(int u,int father){ dfn[u]=low[u]=++id; int ch=0; for(int i=head[u];i;i=edge[i].next){ int x=edge[i].to; if(!dfn[x]){ tarjan(x,father); low[u]=min_(low[u],low[x]); if(low[x]>=dfn[u]&&u!=father) cut[u]=1; if(u==father) ch++; } low[u]=min_(low[u],dfn[x]); } if(ch>=2&&u==father) cut[u]=1; } int main(){ n=read(),m=read(); int u,v; for(int i=1;i<=m;++i){ u=read(),v=read(); add_edge(u,v),add_edge(v,u); } for(int i=1;i<=n;++i){ if(!dfn[i]) tarjan(i,i); } int tot=0; for(int i=1;i<=n;++i){ if(cut[i]) tot++; } printf("%d\n",tot); for(int i=1;i<=n;++i){ if(cut[i]) printf("%d ",i); } puts(""); return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论