[数据结构与算法]Loj#3077-「2019 集训队互测 Day 4」绝目编诗【结论虚树鸽笼原理】

正题

题目链接:https://loj.ac/p/3077

题目大意

给出$n$个点$m$条边的一张简单无向图，求是否存在两个长度相等的简单环。

$1\le n\le 10^4,1\le m\le 10^6$

解题思路

先考虑一个暴力的做法，我们暴力搜索图上的所有环，记$c_i$表示长度为$i$的环的个数。

那么注意到一个长度为$x$的环，我们会重复统计$2x$次（一轮和翻转后的一轮），所以如果$c_x>2x$那么就可以输出$Yes$了。

根据鸽笼原理，我们能注意到图上的环的总数不能超过$n?2$（长度为$3～n$的各一个），否则答案一定是$Yes$。然后考虑在一棵树上，我们每加入一条边后至少增加一个环，所以如果$m\ge 2n?3$的话答案一定是$Yes$，这样我们就成功让$m$就和$n$同级了。

然后考虑如果我们走的每一步都能保证往后是能搜出至少一个环的话，那么一个环最多被统计$2x$次，也就是要搜$2x^2$个点，那么如果答案是$No$我们就最多只需要搜${\sum }_{i=1}^{n}2i^2$也就是$O(n^3)$级别次。

那么如何保证我们走的每个点一定能搜出环，很简单，假设我们的环从$s$出发，我们走到一个点是时暴力$O(n)$地判断它是否能不经过目前重复的走到$s$，如果能那么它搜下去至少会有一个新的环。

这样我们就做到$O(n^4)$的复杂度了。

然后是一个神仙优化

我们假设我们在图上删除$\sqrt{n}$条边，那么每条边被删除的概率就是$\frac{1}{\sqrt{n}}$，假设图恰好长度为$3～n$的环各有一个，那么一个长度为$x$的环没被删除的概率就是$(1?\frac{1}{\sqrt{n}}{)}^x$，同理那最后图上剩下的环的期望个数就是
$$\sum _{i=3}^n{\left(1?\frac{1}{\sqrt{n}}\right)}^i<\frac{1}{1?\left(1?\frac{1}{\sqrt{n}}\right)}=\sqrt{n}$$
所以删除$\sqrt{n}$条边之后图上期望剩下$\sqrt{n}$个环，因为是随机删的，所以如果按照最优去删除的话肯定存在一种方案使得图上剩下不超过$\sqrt{n}$个环。

然后我们指定删一条边肯定能删掉一个环，所以我们只需要删除$2\sqrt{n}$条边就可以使得图上不存在任何一个环，换句话说我只需要删除$2\sqrt{n}$条边就可以让这张图的边数不超过$n?1$，所以这张图的边数不超过$n?1+2\sqrt{n}$。

所以再换句话说，我们就得到了最重要的结论，如果图的边数大于等于$n+2\sqrt{n}$那么答案肯定是$Yes$。

所以我们只需要考虑怎么处理$n+2\sqrt{n}$的情况，我们先找出一棵生成树，然后对于所有的非树边的端点建出一棵虚树，然后连接上非树边，这样我们就得到一张边数和点数都是$\sqrt{n}$级别的图。

不难发现我们上面那种情况也是能处理带权图的（需要注意的是一个长度为$x$的环出现的次数不是$2x$了，我们需要记录这个环在虚树上的边数$s$，如果存在两种不同的边数肯定是两个不同的环，否则就判断出现次数$>2s$），所以我们的复杂度就到了快速的$O(n^2)$了。

因为跑不满并且这是LOJ所以能过。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e4+10;
struct node{
	int to,next,w;
}a[N<<1];
int n,m,tot,cnt,ls[N],dep[N],pos[N];
int las[N],vis[N],dis[N],len[N],c[N];
vector<int> G[N];
void addl(int x,int y,int w){
	a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;
	a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=w;
	return;
}
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;las[x]=fa;int num=0;
	for(int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if(y==fa)continue;
		if(dep[y]){
			if(dep[y]>dep[x])continue;
			if(!pos[x])pos[x]=x;
			if(!pos[y])pos[y]=y;
			addl(pos[x],pos[y],1);
		}
		else{
			dfs(y,x);
			if(pos[y])num=num?-1:pos[y];
		}
	}
	if(!pos[x]&&num<0)pos[x]=x;
	if(pos[x]){
		for(int i=0;i<G[x].size();i++){
			int y=G[x][i];
			if(y==fa)continue;
			if(pos[y]&&las[y]==x)
				addl(pos[x],pos[y],dep[pos[y]]-dep[pos[x]]);
		}
	}
	else pos[x]=num;
	return;
}
bool calc(int x,int fa,int t){
	if(!dep[x])return 1;vis[x]=t;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(i==fa||dep[y]>0||vis[y]==t)continue;
		bool flag=calc(y,i^1,t);
		if(flag)return 1;
	}
	return 0;
}
void solve(int x,int fa){
	if(!calc(x,fa,++cnt))return;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to,r=dis[x]+a[i].w;
		if(i==fa)continue;
		if(!dep[y]){
			if(!len[r])len[r]=dep[x]+1;
			if(len[r]!=dep[x]+1){puts("Yes");exit(0);}
			c[r]++;
			if(c[r]>len[r]*2){puts("Yes");exit(0);}
		}
		if(dep[y]>=0)continue;
		dep[y]=dep[x]+1;dis[y]=dis[x]+a[i].w;
		solve(y,i^1);dep[y]=-1;
	}
	return;
}
int main()
{
//	freopen("4-01.in","r",stdin);
	scanf("%d%d",&n,&m);tot=1;
	if(m>n+sqrt(n)*2.0)return puts("Yes")&0;
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		if(!dep[i])dfs(i,0);
	memset(dep,-1,sizeof(dep));
	for(int i=1;i<=n;i++)
		if(pos[i]==i)
			dep[i]=0,dis[i]=0,solve(i,0),dep[i]=-1;
	puts("No");
	return 0;
}