[2019 集训队互测 Day 4]绝目编诗

题意

给出一个 \(n\) 个点 \(m\) 条边的简单无向图，判断是否存在两个长度相同的简单环。

题解

发现 环的个数超过 \(n\) 的时候，一定有两个长度相同的简单环。

当 \(m\ge 2n\) 的时候，环的个数达到了 \(n+1\)，一定有两个长度相同的环。

所以 \(m\) 比较大的情况就略去了。

在考虑如何暴力，考虑爆搜每个环，我们要做到每走一步都能保证有新的环产生，这样的话找到一个环需要 \(n^3\) 的复杂度（每次往前走一步的时候判一下能否不经过已经走过的点到达），最多 \(n\) 个环，复杂度 \(O(n^4)\)

考虑优化，大胆猜测 \(m-n\) 很小，实际上可以证明是 \(2\sqrt{n}\) 级别的。那么找出一个搜索树之后，找到搜索树以外的边的虚树，那么这个图就变成了只有 \(O(sqrt{n})\) 个点的带权图，跑上面的方法就行了。复杂度 \(O(n^2)\)

结论证明：对于每条边，有 \(\sqrt{n}\) 的概率把他删除的话，期望会删除 \(\sqrt n\) 条边，而长度为 \(c\) 的环保留的概率为 \((1-\frac1{\sqrt{n}})^c\)，那么等比数列求和一下得到期望最终有不超过 \(\sqrt{n}\) 个环，把这些环全部删除后就是树了。

#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,u,v,fa[N],vs[N],p[N],h[N],hd[N],e_num=1,cnt;
vector<int>g[N];
struct edge{
	int v,nxt,w,f;
}e[N<<3];
void add_edge(int u,int v,int w)
{
	e[++e_num]=(edge){v,hd[u],w,0};
	hd[u]=e_num;
}
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void dfs(int x,int y)
{
	if(vs[x])
		p[x]=2;
	int s=0;
	for(int v:g[x])
		if(v^y)
			dfs(v,x),vs[x]|=vs[v],s+=vs[v];
	if(s>1)
		p[x]=2;
}
void sou(int x,int y,int tp,int dep,int d)
{
	if(y&&p[x]==2)
		add_edge(x,tp,dep-d),add_edge(tp,x,dep-d),tp=x,d=dep,p[x]=2;
	else
		p[x]=1;
	for(int v:g[x])
		if(v^y)
			sou(v,x,tp,dep+1,d);
}
int doit(int x,int fr)
{
	p[x]=1;
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].v==fr||e[i].v>fr&&!vs[e[i].v]&&!p[e[i].v]&&doit(e[i].v,fr))
			return 1;
	}
	return 0;
}
int ok(int x,int fr)
{
	memset(p,0,sizeof(p));
	return doit(x,fr);
}
void suo(int x,int fr,int c,int ls)
{
	vs[x]=1;
	for(int i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].f)
			continue;
		e[i^1].f=1;
		if(!vs[e[i].v]&&e[i].v>fr)
		{
			if(ok(e[i].v,fr))
				suo(e[i].v,fr,c+e[i].w,x);
		}
		if(e[i].v==fr)
		{
			if(h[c+e[i].w]>2)
			{
				puts("Yes");
				exit(0);
			}
			h[c+e[i].w]++;
		}
		e[i^1].f=0;
	}
	vs[x]=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	if(m>n+200)
		return puts("Yes"),0;
	int cnt=0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		if(find(u)!=find(v))
			g[u].push_back(v),g[v].push_back(u),fa[find(u)]=find(v);
		else
			vs[u]=vs[v]=1,add_edge(u,v,1),add_edge(v,u,1);
	}
	for(int i=1;i<=n;i++)
		if(!p[i])
			dfs(i,0),sou(i,0,i,0,0),p[i]=2;
	memset(vs,0,sizeof(vs));
	for(int i=1;i<=n;i++)
		suo(i,i,0,i);
	puts("No");
	return 0;
}