loj #3077
Description
给出一个简单无向图，判断是否存在两个长度相同的简单环。
(nle 10^4,mle 10^6)。
Solution
首先考虑朴素做法，从每个点出发暴力搜索，每次回到出发点则计算答案。这样计算的过程中，一个长为 (n) 的环会被从每个节点出发向左右个遍历到一次，一共遍历了 (2n) 次，因此如果长度为 (n) 的环出现了 (>2n) 次，则说明存在两个长度相同的简单环。
考虑优化，因为图中至多存在 (n-2) 个环（长度为 (3sim n)），而在图的一棵生成树上，增加任意一条非树边都会使图中至少多出一个环，因此图中的边数不超过 (n-1+n-2=2n-3) 条，大于 (2n-3) 则答案一定为 (YES).
注意到环长总和最多为 (3+4+dots+nle n^2)，因此如果我们能保证每次遍历都在访问当前没考虑过的环，那么总复杂度就是 (mathcal O(n^3)) 的（每个环被访问 (mathcal O(n)) 次）。而保证这一点也很简单，在走到新的一点时，进行一遍 (dfs) 看从该点能否回到起点，如果能回到则说明这是环边，继续遍历，否则不遍历该点。(dfs) 的复杂度为 (mathcal O(n+m))，因此总复杂度为 (mathcal O(n^4)) 。
这个边的上界依然非常松，能不能卡的更紧一些？
考虑最极限的有长为 (3sim n) 的环各一个的图，在图中随机删边，每条边都有 (sqrt{n}) 的概率被删除，那么删去的边的数量为 (mathcal O(sqrt{n})) ，一个环依然存在的概率为：
其中 (len) 为该环的长度。
因此图中剩余环数量的期望即为：
令 (q=1-dfrac 1{sqrt{n}})，则期望为：
因此图中剩余环数量期望为 (sqrt{n}) ，在此基础上再删去 (sqrt{n}) 条边，就可以是原图没有环，只剩 (n-1) 条边，至此，我们总共只删除了 (2sqrt{n}) 条边，就是原图只剩 (n-1) 条边，因此 (mle n+2sqrt{n})。
在这样的图上再找到一个 (dfs) 树，那么树上有 (mathcal O(sqrt{n})) 条非树边，以这些非树边的顶点建立虚树，再将原图上的非树边加入虚树中，那么原图中的任何一个环都会在虚树上出现。
因此，s我们只需要再虚树这张仅有 (mathcal O(sqrt{n})) 个点的图上跑之前的 (mathcal O(n^4)) 的算法，复杂度为 (mathcal O(n^2)) 的算法，可以通过此题，需要注意的是，新图中某个长度为 (len) 的环被遍历的次数不再是 (2len) 次，而是 (2) 倍的虚树中环上点数，需要额外记录当前环在虚树上的点数 (cnt)。如果新环的 (cnt) 与旧环不同，那么直接 (Yes)，否则根据遍历次数是否 (>2cnt) 进行统计即可。
最终复杂度为 (mathcal O(n^2)) ，可以通过此题。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=2e4+10;
int n,m;
struct node{
int u,v,w,nxt;
};
namespace vt{
node e[M<<1];
int rt,pd[N],tot,ct[N],first[N],cnt=1,siz[N];
bool vis[N];
inline void add(int u,int v,int w){
e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=first[u];first[u]=cnt;
e[++cnt].v=u;e[cnt].w=w;e[cnt].nxt=first[v];first[v]=cnt;
}
inline bool trans(int u,int last){
pd[u]=tot;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].v;
if(i==(last^1)) continue;
if(v==rt) return 1;
if(pd[v]==tot||vis[v]) continue;
if(trans(v,i)) return 1;
}
return 0;
}
inline void dfs(int u,int fa,int last,int len,int sum){
++tot;
if(!trans(u,last)) return ;
vis[u]=1;
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].v;
if(i==(last^1)) continue;
if(vis[v]){
if(v!=rt) continue;
int now=sum+e[i].w;
if(!siz[now]){siz[now]=len;ct[now]=1;continue;}
if(siz[now]!=len){puts("Yes");exit(0);}
if((++ct[now])>(len<<1)){puts("Yes");exit(0);}
}
else dfs(v,u,i,len+1,sum+e[i].w);
}
vis[u]=0;
}
inline void solve(){
for(int i=1;i<=n;++i) rt=i,dfs(i,0,0,1,0);
puts("No");
}
}
int stk[N],top;
namespace Rt{
node e[M<<1];
int first[N],cnt,dfn[N],tot,pa[N][15],dep[N],s[N];
inline void add(int u,int v){e[++cnt].v=v;e[cnt].u=u;e[cnt].nxt=first[u];first[u]=cnt;}
inline void dfs(int u,int fa){
dfn[u]=++tot;dep[u]=dep[fa]+1;
pa[u][0]=fa;
for(int i=1;(1<<i)<=dep[u];++i) pa[u][i]=pa[pa[u][i-1]][i-1];
for(int i=first[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
if(dfn[v]){
if(dfn[v]>dfn[u]) stk[++top]=u,stk[++top]=v,vt::add(u,v,1);
}
else dfs(v,u);
}
}
inline bool cmp(const int &x,const int &y){return dfn[x]<dfn[y];}
inline int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
int t=dep[u]-dep[v];
for(int i=14;i>=0;--i) if(t&(1<<i)) u=pa[u][i];
if(u==v) return u;
for(int i=14;i>=0;--i) if(pa[u][i]!=pa[v][i]) u=pa[u][i],v=pa[v][i];
return pa[u][0];
}
inline int getdis(int u,int v){return dep[u]+dep[v]-2*dep[LCA(u,v)];}
inline void build(){
sort(stk+1,stk+top+1,cmp);
int m=unique(stk+1,stk+top+1)-stk-1;
s[top=1]=stk[1];
for(int i=2;i<=m;++i){
int u=stk[i],lca=LCA(s[top],u);
while(top>1&&dep[lca]<=dep[s[top-1]])
vt::add(s[top-1],s[top],getdis(s[top-1],s[top])),top--;
if(s[top]!=lca) vt::add(lca,s[top],getdis(s[top],lca)),s[top]=lca;
s[++top]=u;
}
while(top>1) vt::add(s[top-1],s[top],getdis(s[top-1],s[top])),top--;
}
}
using namespace Rt;
int main(){
scanf("%d%d",&n,&m);
if(m>=n+2*sqrt(n)){puts("Yes");return 0;}
for(int i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n;++i){
if(!dfn[i]){
top=0;
dfs(i,0);
build();
}
}
vt::solve();
return 0;
}