![[BZOJ]1064: [Noi2008]假面舞会 [BZOJ]1064: [Noi2008]假面舞会](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700)
题目大意:n个人,k种假面,每人戴一种,戴第i种的可以看见第i+1种,戴第k种的可以看见第1种,给出m条关系表示一个人可以看到另一个人,问k可能的最大值和最小值。(n<=100,000,m<=1,000,000)
思路:染色,若点i颜色为ci,就把点i能到的点染成ci+1,能到点i的点染成ci-1,如果染之前已经染过了,设要染的点为j,则cj和ci+1(-1)模k同余,若cj不等于ci+1(-1),则k必然为|ci+1(-1)-cj|的因子,取gcd即可。若没有出现这种情况,最大答案为各连通块最长链的和。(稍微卡了个常卡到rank1 233)
#include<cstdio>
#include<algorithm>
using namespace std;
char B[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define r register int
#define MN 100000
#define MM 1000000
struct edge{int nx,t;}e[MM*+];
int h[MN+],rh[MN+],en,c[MN+],ans,mn,mx;
inline void ins(int*h,int x,int y){e[++en]=(edge){h[x],y};h[x]=en;}
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline int z(int x){return x<?-x:x;}
void dfs(int x)
{
for(r i=h[x];i;i=e[i].nx)
c[e[i].t]?ans=gcd(ans,z(c[e[i].t]-c[x]-)):
(mx=max(mx,c[e[i].t]=c[x]+),dfs(e[i].t),);
for(r i=rh[x];i;i=e[i].nx)
c[e[i].t]?ans=gcd(ans,z(c[e[i].t]-c[x]+)):
(mn=min(mn,c[e[i].t]=c[x]-),dfs(e[i].t),);
}
int main()
{
fread(B,,<<,stdin);
int n,m,x,y,i,s=;
n=read();m=read();
while(m--)x=read(),ins(h,x,y=read()),ins(rh,y,x);
for(i=;i<=n;++i)if(!c[i])c[i]=mn=mx=n,dfs(i),s+=mx-mn+;
if(ans)
{
if(ans<)return *puts("-1 -1");
for(i=;i<=ans;++i)if(ans%i==)break;
return *printf("%d %d\n",ans,i);
}
printf("%d %d\n",s<?-:s,s<?-:);
}