Tarjan:强连通分量 割点
有时间写
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
#include<cstdio> #include<iostream>
#define MogeKo qwq
using namespace std; const int maxn = 100005; int n,m,a,b,sum,ans; int now,top,num; int dfn[maxn],low[maxn],sta[maxn],out[maxn],col[maxn]; int cnt,to[maxn],nxt[maxn],head[maxn]; bool insta[maxn]; void add(int x,int y) { to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; } void Tarjan(int u) { dfn[u] = low[u] = ++now; sta[++top] = u; insta[u] = true; for(int i = head[u]; i; i = nxt[i]) { int v = to[i]; if(!dfn[v]) { Tarjan(v); low[u] = min(low[u],low[v]); } else if(insta[v]) low[u] = min(low[u],dfn[v]); } if(low[u] == dfn[u]) { col[u] = ++num; insta[u] = false; while(sta[top]!=u) { int v = sta[top]; col[v] = num; insta[v] = false; top--; } top--; } } int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= m; i++) { scanf("%d%d",&a,&b); add(a,b); } for(int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i); for(int u = 1; u <= n; u++) for(int i = head[u]; i; i = nxt[i]) { int v = to[i]; if(col[u] != col[v]) out[col[u]]++; } for(int i = 1; i <= num; i++) { if(!out[i]) { if(ans) { printf("0"); return 0; } for(int u = 1; u <= n; u++) if(col[u] == i)ans++; } } printf("%d",ans); return 0; }
View Code
#include<cstdio> #include<iostream> #include<cstring> #include<cmath>
#define MogeKo qwq
using namespace std; const int maxn = 1e6+10; const int INF = 2147483647; int n,m,cnt,now,num,top,sum; int x,y,z; int to[maxn],head[maxn],nxt[maxn]; int dfn[maxn],low[maxn]; bool iscut[maxn]; void add(int x,int y) { to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; } void Tarjan(int u,int fa) { dfn[u] = low[u] = ++now; int ch = 0; for(int i = head[u]; i; i = nxt[i]) { int v = to[i]; if(!dfn[v]) { if(fa == u)ch++; Tarjan(v,fa); low[u] = min(low[u],low[v]); if(fa != u && low[v] >= dfn[u]) iscut[u] = true; } low[u] = min(low[u],dfn[v]); if(fa == u && ch >= 2) iscut[u] = true; } } int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= m; i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i,i); for(int i = 1; i <= n; i++) if(iscut[i])sum++; printf("%d\n",sum); for(int i = 1; i <= n; i++) if(iscut[i]) printf("%d ",i); return 0; }
View Code
更多精彩
