缩点
对于一个强连通分量，里面的所有点都是等效的，任意一个点被欢迎等价于全部被欢迎，任意一个去欢迎等价于全部去欢迎，于是把他们缩起来。
缩完得到一棵树，只需判断出度为零点是否唯一即可
#include<cstdio> #include<algorithm> #define N 10005 #define M 50005 using namespace std; struct edge{int next,to;}e[M]; int ecnt=0, last[N], cnt=0, dfn[N], low[N], sta[N], top=0, times=0, belong[N], siz[N]; bool out[N]; void add(int a, int b) { e[++ecnt]=(edge){last[a],b}; last[a]=ecnt; } void tarjan(int x) { sta[++top]=x; dfn[x]=low[x]=++times; for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; if(dfn[y])low[x]=min(low[x],dfn[y]); else{tarjan(y);low[x]=min(low[x],low[y]);} } if(dfn[x]==low[x]) { ++cnt; siz[cnt]=1; while(sta[top]!=x) { belong[sta[top--]]=cnt; siz[cnt]++; } belong[sta[top--]]=cnt; } } int main() { int n, m; scanf("%d%d",&n,&m); for(int i = 1, a, b; 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 x = 1; x <= n; x++) for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; if(belong[x]!=belong[y]) out[belong[x]]=1; } int ans=0; for(int i = 1; i <= cnt; i++) if(!out[i]) { if(ans)return !printf("0\n"); ans=siz[i]; } printf("%d\n",ans); return 0; }