原题链接
绝望 我又一次忘记了 那是位置 应该用num[i] 而不应该用i
依旧是Tarjan 一看就知道 和上次的爱心天使 十分类似
但是 我还是卡了 很长时间
因为 我又一次忘记了 那是位置
来自绝望的 江之岛·怎么又是这样·伊凡
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<queue> using namespace std; int dfni,dfn[10000+5],low[10000+5],vis[10000+5],top,st[10000+5]; int f,p,pc,ans,head[10000+5],nxt[100000+5],num[100000+5],clo,tot,n,m,a,b,clor[10000+5],flag[10000+5]; void tarjan(int x) { int i; dfni++; dfn[x]=dfni; low[x]=dfni; vis[x]=1; top++; st[top]=x; for(i=head[x];i;i=nxt[i]) { if(!dfn[num[i]]) { tarjan(num[i]); low[x]=min(low[x],low[num[i]]); } else if(vis[num[i]]) low[x]=min(low[x],low[num[i]]); } if(low[x]==dfn[x]) { vis[x]=0; clo++; clor[x]=clo; while(st[top]!=x) { clor[st[top]]=clo; vis[st[top]]=0; top--; } top--; } } void add(int p1,int p2) { tot++; num[tot]=p2; nxt[tot]=head[p1]; head[p1]=tot; } int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); } for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(i=1;i<=n;i++) for(k=head[i];k;k=nxt[k]) if(clor[i]!=clor[num[k]]) { flag[clor[i]]=1; } for(i=1;i<=clo;i++) { if(!flag[i]) { p++; pc=i; } if(p>1) { printf("0"); return 0; } } if(!p) { printf("0"); return 0; } for(i=1;i<=n;i++) if(clor[i]==pc) ans++; printf("%d",ans); return 0; }