题意
给出一个 \(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;
}