OLZ BYVOID神犇题解:
https://www.byvoid.com/blog/noi-2008-party/
顶点标号的技巧很巧妙OLZ
AC code:
#include <cstdio>
const int N=100010;
const int M=1000010;
int n,m,cnt=1,tot,cb,top;
int head[N],num[N],a[N],bl[N],stk[N],minn[N],maxn[N];
bool ins[N];
struct Edge{
int u,v,w,next;
Edge() {}
Edge(int u,int v,int w,int next):u(u),v(v),w(w),next(next) {}
}E[M];
int Abs(int x){
return x<0?-x:x;
}
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
int Max(int x,int y){
return x>y?x:y;
}
int Min(int x,int y){
return x<y?x:y;
}
void addedge(int u,int v){
E[++cnt]=Edge(u,v,1,head[u]);
E[++cnt]=Edge(v,u,-1,head[v]);
head[u]=cnt-1;head[v]=cnt;
}
void read(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
}
}
void DFS(int x,int cnum){
num[x]=cnum;bl[x]=cb;ins[x]=1;stk[++top]=x;
for(int i=head[x];i;i=E[i].next){
if(bl[E[i].v]){
if(ins[E[i].v]&&stk[top-1]!=E[i].v&&cnum+E[i].w-num[E[i].v])
a[++tot]=Abs(cnum+E[i].w-num[E[i].v]);
continue ;
}
DFS(E[i].v,cnum+E[i].w);
ins[E[i].v]=0;top--;
}
}
int main(){
read();
for(int i=1;i<=n;i++){
if(!bl[i]){
cb++;
DFS(i,1);
}
}
if(tot){
int ans=a[1];
for(int i=2;i<=tot;i++) ans=gcd(ans,a[i]);
if(ans<3) printf("-1 -1\n");
else{
for(int i=3;i<=ans;i++){
if(!(ans%i)){
printf("%d %d\n",ans,i);
break;
}
}
}
}
else{
int ans=0;
for(int i=1;i<=n;i++) minn[i]=1<<28;
for(int i=1;i<=n;i++){
minn[bl[i]]=Min(minn[bl[i]],num[i]);
maxn[bl[i]]=Max(maxn[bl[i]],num[i]);
}
for(int i=1;i<=n;i++) if(maxn[i]) ans+=maxn[i]-minn[i]+1;
if(ans<3) printf("-1 -1\n");
else printf("%d 3\n",ans);
}
return 0;
}