目录
显示
题目链接
https://www.luogu.com.cn/problem/P1477
题解
如果整个图没有环的话，显然最多能分的种类数是每个连通分量内最长链的长度之和。
如果整个图是由若干个不相交的环构成的话，最多能分的种类数是所有环长度的最大公约数（找环的时候，可以从连通块内的任意一点开始编号，第二次经过一个点的时候，它第二次的编号减去第一次的编号就是环的大小）。
除了这两种特殊情况之外，还有一种情况是两个环之间可能有公共部分。
我们 DFS 的时候可以倒推：建图的时候不仅连一条 \(u \to v\)，边权为 \(1\) 的边之外，同时连一条 \(v \to u\)，边权为 \(-1\) 的边（这种连边方式可以确保我们从任意一个点开始，都可以遍历整个连通块）。
对于每个连通块，我们还是任意选一个点开始编号，经过一条边的时候将编号加上边权，和上面一样，第二次经过同一个点的时候，它第二次的编号减去第一次的编号就是环的大小。
这样我们就可以找出所有的环了。
（最后别忘了题目要求面具最少要有三种）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define INF 1e9
using namespace std;
struct edge
{
int v,w;
bool operator<(const edge&a)const
{
return v<a.v||(v==a.v&&w<a.w);
}
};
set<edge> e[100005];
int dis[100005],vis[100005],ans,res,cnt,maxv,minv;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
void dfs(int u,int d)
{
if(dis[u])
{
ans=gcd(ans,abs(d-dis[u]));
return;
}
dis[u]=d,vis[u]=1;
maxv=max(maxv,dis[u]);
minv=min(minv,dis[u]);
for(auto i:e[u])
dfs(i.v,d+i.w);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
e[u].insert({v,1});
e[v].insert({u,-1});
}
for(int i=1;i<=n;i++)
if(!vis[i])
{
maxv=-INF,minv=INF;
dfs(i,1);
res+=maxv-minv+1;
}
if(ans)
{
if(ans<3)puts("-1 -1");
else
for(int i=3;i<=ans;i++)
if(ans%i==0)
{
printf("%d %d\n",ans,i);
break;
}
}
else
{
if(res<3)puts("-1 -1");
else printf("%d 3\n",res);
}
return 0;
}