这道题显然就是一个tarjan缩点搞搞之后就过了
看出度为0的点是否只有一个 如果是则这个点能被所有点到达 否则没有能被所有点到达的
先缩点，然后看出度为0的强连通分量是否只有一个 如果有，则答案为这个强连通分量的大小 否则没有能被所有点到达的点
所以缩点即可，1A过
#include<cstdio> #include<iostream> #include<cstring> #define MAXN 50000+10 using namespace std; struct Line{ int from,to,nxt; }line[MAXN]; int head[MAXN],tail,timer,stack[MAXN],vis[MAXN],dfn[MAXN],low[MAXN],t[MAXN],cnt,top,size[MAXN]; int n,m,out[MAXN],ss; void add_line(int from,int to){ tail++; line[tail].from=from; line[tail].to=to; line[tail].nxt=head[from]; head[from]=tail; } void tarjan(int x){ dfn[x]=low[x]=++timer; stack[++top]=x; vis[x]=true; for(int i=head[x];i;i=line[i].nxt){ int v=line[i].to; if(!dfn[v]){ tarjan(v); low[x]=min(low[x],low[v]); }else{ if(vis[v]){ low[x]=min(low[x],dfn[v]); } } } if(low[x]==dfn[x]){ vis[x]=false; cnt++; size[cnt]++; t[x]=cnt; while(stack[top]!=x){ vis[stack[top]]=false; t[stack[top]]=cnt; size[cnt]++; top--; } top--; } } int main(){ scanf("%d%d",&n,&m); for(register int i=1;i<=m;i++){ int f,t; scanf("%d%d",&f,&t); add_line(f,t); } for(register int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } for(int i=1;i<=n;i++){ for(int j=head[i];j;j=line[j].nxt){ int v=line[j].to; if(t[i]!=t[v]) out[t[i]]++; } } int ccc; bool judge=false; for(int i=1;i<=cnt;i++){ if(out[i]==0){ if(judge==true){ printf("0"); return 0; }else{ judge=true; ss=size[i]; } } } printf("%d",ss); return 0; }