「NOI2008」假面舞会 - 图的遍历+最大公约数

题目大意

    一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。
    今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。
    为了使舞会更有神秘感，主办方把面具分为$k(k\ge3)$类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第$i$类面具的人才能看到戴第$i+1$类面具的人的编号，戴第$k$类面具的人能看到戴第$1$类面具的人的编号。
    参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。
    栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第$2$号面具的人看到了第$5$号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。
    由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。
    由于主办方已经声明了$k\ge3$，所以你必须将这条信息也考虑进去。

---

题目分析

本题很特别，需要寻找一定的规律，再使用图论知识解决。

我们发现如果图中有环，那么答案必定由环限制，因为树的最小值显然是$1$。

因此，首先考虑题目不存在环的情况，即一个森林。
森林的最小值显然是$\max(1,3)=3$，最大值为每棵树最长链相加。

考虑，若图中存在环，那么对于一个环，所有环长的约数均可成为答案。
但是一个这样的“环”也可以对答案做出贡献：

其贡献是$\left|a-b\right|$的所有约数，其中$a,b$是该“环”上的两条有向链。
因此我们不妨将原图每一条边对应一条$-1$的反边，找出所有环取$\gcd$即为最大的答案。
然而，找出所有环是没有多项式算法的。
注意到我们只需要求出环的$\gcd$，根据$\gcd$的性质，我们只需要求出Dfs/Bfs树上的返祖边构成的环即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005;

struct Edge {
	int from,to,dist;
};

int n,m,Dist[maxn],Gcd=0,sum=0;
bool vst[maxn];
vector<Edge>edges[maxn];

void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {x,y,v});
}

int Bfs(int s) {
	Dist[s]=0;
	int Max=0,Min=0;
	queue<int>Q;
	Q.push(s);
	while(!Q.empty()) {
		int Now=Q.front();
		Max=max(Max,Dist[Now]);
		Min=min(Min,Dist[Now]);
		Q.pop();
		for(Edge& e:edges[Now]) {
			int Next=e.to;
			if(vst[Next]) { //环 
				Gcd=__gcd(Gcd,abs(Dist[Now]+e.dist-Dist[Next]));
				continue;
			}
			vst[Next]=1;
			Dist[Next]=Dist[Now]+e.dist;
			Q.push(Next);
		}
	}
	return Max-Min+1;
}

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int();
		AddEdge(x,y,1);
		AddEdge(y,x,-1);
	}
	for(int i=1; i<=n; i++)
		if(!vst[i])sum+=Bfs(i);
	if(Gcd) {
		if(Gcd<3)puts("-1 -1");
		else if(Gcd>=1) {
			for(int i=3; i<=Gcd; i++)
				if(Gcd%i==0) {
					printf("%d %d\n",Gcd,i);
					break;
				}
		}
	} else if(sum<3)puts("-1 -1");
	else printf("%d 3",sum);
	return 0;
}