首页 > 代码库 > bzoj1051
bzoj1051
就是一个tarjan
#include<iostream> #include<stack> #include<cstdio> using namespace std; struct edge { int to,nxt,from; }e[100011]; int Color,cnt=1,n,m,tot,Time,p,ans; stack<int>s; int color[10010],dfn[10010],low[10010],in[10010],g[10010]; inline void link(int u,int v) { e[++cnt].nxt=g[u]; e[cnt].from=u; g[u]=cnt; e[cnt].to=v; } inline int read() { int x=0,f=1; char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x*=10;x+=c-‘0‘;c=getchar();} return x*f; } inline int Min(int x,int y) { return x<y?x:y; } void tarjan(int u) { dfn[u]=low[u]=++Time; s.push(u); for(int i=g[u];i;i=e[i].nxt) { int v=e[i].to; if(!dfn[v]) { tarjan(v); } if(dfn[v]!=-1) low[u]=Min(low[u],low[v]); } if(dfn[u]==low[u]) { ++Color; while(!s.empty()) { int x=s.top(); s.pop(); dfn[x]=-1; color[x]=Color; if(x==u) break; } } } int main() { n=read(); m=read(); for(int i=1;i<=m;i++) { int u,v; u=read(); v=read(); link(u,v); } for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } for(int i=1;i<=cnt;i++) { int u=e[i].from,v=e[i].to; if(color[u]!=color[v]) in[color[u]]++; } for(int i=1;i<=Color;i++) { if(!in[i]) { tot++; p=i; if(tot==2) { printf("%d",0); return 0; } } } for(int i=1;i<=n;i++) if(color[i]==p) ans++; printf("%d",ans); return 0; }
bzoj1051
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。