按照关系建立又向边，缩点为DAG图，重新构图，判断是否有且仅有一个出度为0的点，如果是，这个点所代表的环上的点数就是答案。
否侧，不存在~
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <algorithm> 6 7 #define N 111111 8 #define M 555555 9 10 using namespace std; 11 12 struct S 13 { 14 int a,b; 15 }s[M]; 16 17 int n,m,divg,gs,cnt,tle,res,ans; 18 int head[N],next[M],to[M]; 19 int out[N],belong[N],dfn[N],low[N],num[N],stk[N],q[N]; 20 bool fg[N]; 21 22 inline void add(int u,int v) 23 { 24 to[cnt]=v; next[cnt]=head[u]; head[u]=cnt++; 25 } 26 27 inline void read() 28 { 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=m;i++) 31 scanf("%d%d",&s[i].a,&s[i].b); 32 } 33 34 inline void dfs(int u) 35 { 36 dfn[u]=low[u]=++tle; 37 stk[++gs]=u; fg[u]=true; 38 for(int i=head[u];~i;i=next[i]) 39 { 40 if(!dfn[to[i]]) 41 { 42 dfs(to[i]); 43 low[u]=min(low[u],low[to[i]]); 44 } 45 else if(fg[to[i]]) low[u]=min(dfn[to[i]],low[u]); 46 } 47 if(dfn[u]==low[u]) 48 { 49 divg++; int tmp=-1; 50 while(tmp!=u) 51 { 52 tmp=stk[gs--]; 53 belong[tmp]=divg; 54 num[divg]++; 55 fg[tmp]=false; 56 } 57 } 58 } 59 60 inline void go() 61 { 62 memset(head,-1,sizeof head); cnt=0; 63 for(int i=1;i<=m;i++) add(s[i].a,s[i].b); 64 for(int i=1;i<=n;i++) 65 if(!dfn[i]) dfs(i); 66 memset(head,-1,sizeof head); cnt=0; 67 for(int i=1;i<=m;i++) 68 if(belong[s[i].a]!=belong[s[i].b]) out[belong[s[i].a]]++; 69 for(int i=1;i<=divg;i++) 70 if(out[i]==0) res++,ans=i; 71 if(res==1) printf("%d\n",num[ans]); 72 else puts("0"); 73 } 74 75 int main() 76 { 77 read(),go(); 78 return 0; 79 }