BZOJ 1064 NOI 2008仮面舞踏会DFS

指定のn人、それぞれk種類の仮面をかぶって(k>=3、k未知)、その中でi種類の仮面をかぶっている人はi%k+1種類の人の仮面を見ることができて、いくつかの人の互いに見る関係を与えて、kの最大の最小値を求めます
問題を解く. http://www.cnblogs.com/proverbs/archive/2013/01/17/2865093.html
DFSリング長を求める
なお、図中にリングが存在しない場合のkの最大値は、すべての連通図における最長チェーンの長さの和である
正の辺の重みの値が+1の負の辺の重みの値が-1でGCDを計算する時絶対値を取ることに注意します

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100100
using namespace std;
struct abcd{
	int to,f,next;
}table[1001001];
int head[M],f[M],tot=1;
int n,m,ansmax,ansmin,lmax,lmin;
bool v[M];
int GCD(int x,int y)
{
	if(y==0) return x;
	return GCD(y,x%y);
}
void dfs1(int x)
{
	int i;
	v[x]=1;
	for(i=head[x];i;i=table[i].next)
	{
		if(!v[table[i].to])
			f[table[i].to]=f[x]+table[i].f,dfs1(table[i].to);
		else
			ansmax=GCD(ansmax, abs(f[x]+table[i].f-f[table[i].to]) );
	}
}
void dfs2(int x)
{
	int i;
	v[x]=1;
	lmax=max(lmax,f[x]);
	lmin=min(lmin,f[x]);
	for(i=head[x];i;i=table[i].next)
		if(!v[table[i].to])
		{
			f[table[i].to]=f[x]+table[i].f;
			dfs2(table[i].to);
		}
}
void add(int x,int y,int z)
{
	table[++tot].to=y;
	table[tot].f=z;
	table[tot].next=head[x];
	head[x]=tot;
}
int main()
{
	
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	
	int i,x,y;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y,1);
		add(y,x,-1);
	}
	for(i=1;i<=n;i++)
		if(!v[i])
			dfs1(i);
	if(ansmax)
		for(ansmin=3;ansmin<ansmax&&ansmax%ansmin;ansmin++);
	else
	{
		memset(v,0,sizeof v);
		memset(f,0,sizeof f);
		for(i=1;i<=n;i++)
			if(!v[i])
			{
				lmax=lmin=0;
				dfs2(i);
				ansmax+=lmax-lmin+1;
			}
		ansmin=3;
	}
	if(ansmax<3)
		ansmax=ansmin=-1;
	printf("%d %d
",ansmax,ansmin);
}