题意:有n个人，每个人都有一个标号，每种标号的人只能看见下一个标号的人（最后一种标号看见第一种），给定m个关系，求这个关系是否合法以及合法情况下最大和最小的方案数。$nleqslant 10^{5},mleqslant 10^{6}$
题解：如果有环的话，答案最大就是环的长度的gcd，最小是gcd的最小的大于2的因数。如果没有环的话，答案是最长链长度之和，最小是3.然后我们直接暴力染色就好啦
#include#include #define MN 100000 using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }bool found=false; bool inq[MN+5],mark[MN+5]; int n,m,head[MN+5],cnt=0,ans=0,top=0,q[MN+5],f[MN+5],mx,mn; struct edge{ int to,next,kind;}e[MN*20+5];void ins(int f,int t){e[++cnt]=(edge){t,head[f],1};head[f]=cnt;e[++cnt]=(edge){f,head[t],0};head[t]=cnt; }inline int gcd(int x,int y){ return (!y)?x:gcd(y,x%y);} inline int abs(int x){ return x>0?x:-x;}void check(int x) {x=abs(x);if(!x)return;if(!found) found=true,ans=x;else ans=gcd(ans,x); }void solve(int x) {mx=max(mx,f[x]);mn=min(mn,f[x]);mark[x]=1;for(int i=head[x];i;i=e[i].next){if(!mark[e[i].to]) (f[e[i].to]=f[x]+(e[i].kind?1:-1)),solve(e[i].to);if((f[e[i].to]-f[x]-(e[i].kind?-1:1))!=0)check(f[e[i].to]-f[x]+(e[i].kind?-1:1));} }int get(int x) {for(int i=3;i<=x;i++)if(x%i==0)return i; }int main() {n=read();m=read();if(n<=2) return 0*puts("-1 -1");for(int i=1;i<=m;i++){ int u=read(),v=read();ins(u,v);}int sum=0;for(int i=1;i<=n;i++)if(!mark[i])mx=mn=0,f[i]=0,solve(i),sum+=mx-mn+1;if(found) printf("%d %d ",ans>2?ans:-1,ans>2?get(ans):-1);else printf("%d %d ",sum>2?sum:-1,sum>2?3:-1);return 0; }