QAQ 详见爱在心中。这个输出符合条件的强联通分量里面的点的数量
#include <cstdio> #include <iostream> using namespace std; int head[10001],net[200000],to[200000]; int cnt; int n,m; void add(int x,int y) { cnt++; to[cnt]=y; net[cnt]=head[x]; head[x]=cnt; } int color[10001],c,num,low[10001],dfn[10001],top,f[10001],s[10001]; int sum[10001]; int flag[10001]; void dfs(int x) { dfn[x]=++num; low[x]=num; f[x]=1; s[++top]=x; for(int i=head[x];i;i=net[i]) { int tmp=to[i]; if(dfn[tmp]==0) { dfs(tmp); low[x]=min(low[x],low[tmp]); } else if(f[tmp]==1) { low[x]=min(low[x],dfn[tmp]); } } if(low[x]==dfn[x]) { f[x]=0; color[x]=++c; int tot=1; while(s[top]!=x) { color[s[top]]=c; f[s[top]]=0; top--; tot++; } top--; sum[c]=tot; } } void find() { for(int i=1;i<=n;i++) for(int j=head[i];j;j=net[j]) { int tmp=to[j]; if(color[i]!=color[tmp]) flag[color[i]]=1; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i); find(); int k=0; int p; for(int i=1;i<=c;i++) if(!flag[i]) { k++; p=i; } if(k!=1) printf("0"); else printf("%d",sum[p]); return 0; }