题面纯英文……就不粘题面了。
简单的说，就是将图强连通分量缩点，然后拓扑一下。 为了避免拓扑，我们可以反向存图，然后查入度为0的点即可。#include#include #include #include #include using namespace std;typedef long long ll;inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w;}const int maxn=10001;int cnt=0,head[maxn]; struct node{ int w; int to; int nxt;}edge[50001];void add(int u,int v){ cnt++; edge[cnt].to=v; edge[cnt].nxt=head[u]; head[u]=cnt; return;}int dfn[maxn]; int low[maxn];bool instack[maxn];int dis[maxn];int indeg[maxn];int to[maxn];int t=0,l=0;stack q;void tarjan(int u){ int v; t++; dfn[u]=t; low[u]=t; q.push(u); instack[u]=1; for(int i=head[u];i!=0;i=edge[i].nxt){ v=edge[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ l++; do{ v=q.top(); q.pop(); instack[v]=0; to[v]=l; dis[l]++; }while(v!=u); } return;}int main(){ int n=read(); int m=read(); for(int i=1;i<=m;i++){ int u=read(); int v=read(); add(v,u); } for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i); } } cnt=0; for(int i=1;i<=n;i++){ for(int j=head[i];j;j=edge[j].nxt){ int u=to[i]; int v=to[edge[j].to]; if(u!=v){ indeg[v]++; } } } int ans=-1; for(int i=1;i<=l;i++){ if(indeg[i]==0){ if(ans==-1)ans=dis[i]; else{ printf("0\n"); return 0; } } } if(ans==-1)printf("0\n"); else printf("%d\n",ans); return 0;}