[文章目录]
Description
每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为k (k≥3)类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第i 类面具的人才能看到戴第i+1 类面具的人的编号，戴第k 类面具的人能看到戴第1 类面具的人的编号。 参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。 栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第2号面具的人看到了第5 号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信 息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。由于主办方已经声明了k≥3，所以你必须将这条信息也考虑进去。n<=10^5 m<=10^6
如果有环的话，所有环长的gcd即为答案。如果无环，联通的拓扑图的最长链上点的个数的和加上即为答案。
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
const int inf=0x3f3f3f3f;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
return x;
}
int n,m,sum,cir,head[N],to[2001000],nxt[2001000],f[2001000],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x];
head[x]=cnt; f[cnt]=z;
}
inline int Abs(int x){return x>0?x:-x;}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
queue<int>q;
int dis[N],b[N],mi,mx;
bool vis[N];
void bfs(int x)
{
vis[x]=1; q.push(x); int i; mx=mi=0;
while(!q.empty())
{
x=q.front(); q.pop(); mi=min(mi,dis[x]); mx=max(mx,dis[x]);
for(i=head[x];i;i=nxt[i])
{
if(!vis[to[i]]) vis[to[i]]=1,dis[to[i]]=dis[x]+f[i],q.push(to[i]);
else cir=gcd(cir,Abs(dis[x]+f[i]-dis[to[i]]));
}
}
}
int main()
{
n=read(); m=read();
int i,x,y;
for(i=1;i<=m;++i)
{
x=read(); y=read();
add(x,y,1); add(y,x,-1);
}
for(i=1;i<=n;++i) if(!vis[i]) bfs(i),sum+=mx-mi+1;
if(!cir)
{
if(sum>=3) printf("%d 3\n",sum);
else puts("-1 -1");
}
else
{
for(y=3;y<=cir;++y) if(cir%y==0) break;
if(cir>=3) printf("%d %d\n",cir,y);
else puts("-1 -1");
}
return 0;
}