将图中的环的长度定义为正向边数量-反向边数量，那么答案一定是所有环的环长的共同因子。dfs一下就能找到图中的一些环，并且图中的所有环的环长都可以由这些环长加加减减得到（好像不太会证）。如果有环长为1或2则无解。
没有环的话图就是一个有向树。类似定义链的长度，那么一个连通块内答案就是最长链，也即dfs树上最大深度-最小深度+1，对所有连通块累加即可。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 100010#define M 1000010int n,m,p[N],deep[N],t=0,ans=0,mx,mn;bool flag[N];struct data{ int to,nxt,len;}edge[M];void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}void dfs(int k,int from){ if (ans==-1) return; flag[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { if (!flag[edge[i].to]) deep[edge[i].to]=deep[k]+edge[i].len,dfs(edge[i].to,k); else if (abs(deep[k]-deep[edge[i].to]+edge[i].len)==1||abs(deep[k]-deep[edge[i].to]+edge[i].len)==2) {ans=-1;return;} else ans=gcd(ans,abs(deep[k]-deep[edge[i].to]+edge[i].len)); }}void find(int k){ flag[k]=1;mn=min(mn,deep[k]),mx=max(mx,deep[k]); for (int i=p[k];i;i=edge[i].nxt) if (!flag[edge[i].to]) find(edge[i].to);}int main(){#ifndef ONLINE_JUDGE freopen("bzoj1064.in","r",stdin); freopen("bzoj1064.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(); addedge(x,y,1),addedge(y,x,-1); } for (int i=1;i<=n;i++) if (!flag[i]) dfs(i,i); if (ans==-1) {cout<<-1<<' '<<-1;return 0;} else if (ans==0) { memset(flag,0,sizeof(flag)); for (int i=1;i<=n;i++) if (!flag[i]) mx=-N,mn=N,find(i),ans+=mx-mn+1; if (ans>2) cout< <<' '<<3;else cout<<-1<<' '<<-1; } else for (int i=3;i<=ans;i++) if (ans%i==0) {cout< <<' '<