题目大意

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

\(1 \le n \le 10^4 , 1 \le m \le 10^6\)。

思路

考虑暴力怎么做。

我们可以对于每个点，搜出包含这个点的环。

那么我们就有了一个玄学复杂度的暴力。考虑优化。

因为一个无向图的简单环长度只可能在 \([3,n]\) 的区间内，一共 \(n-2\) 个，所以长度之和为 \(n^2\) 级别。因为每个环我们会遍历两倍长度次，所以如果我们只访问环上的边，我们就可以达到 \(O(n^3)\) 的复杂度。

为了只遍历环边，我们每到一个点都用一个 \(O(n)\) 的 dfs 判断当前点是否可能构成环，即判断当前点是否可以不通过搜索栈中的节点到达起点。这样，我们的整体复杂度就是 \(O(n^4)\) 的。

这样显然不能过，而且暴力已经不好优化了，所以考虑减少 \(n\) 的规模。

考虑一个图简单环长度两两不同时，最多有多少条边。

直接想比较困难，考虑一颗树最多可以加入多少条边，使得简单环长度两两不同。

首先对于一颗树，每加入一条边至少会产生一个简单环。

要让加入的边数最大，我们肯定要让每一条边只形成一个简单环。

根据简单环的定义，我们发现，只有两个简单环交点个数小于等于 \(1\) 时，它们才不会构成新的简单环。

那么一个简单的构造方法就是先让一个点作为所有简单环的交点，然后在这个点上挂环。

考虑现在有 \(n\) 个点，我们选定 \(1\) 号节点作为交点。

我们挂一个长度为 \(x\) 的环，需要 \(x-1\) 个点和 \(x\) 条边。

我们从长度为 \(3\) 的环开始，长度从小到大依次往上挂。

那么假设我们挂完了长度小于等于 \(t\) 的环，我们用的点数（包括 \(1\) 号节点）\(cnt\) 为 \(1+\underset{i=3}{\overset{t}{\sum}}i-1=\underset{i=1}{\overset{t-1}{\sum}}i=\frac{t \times (t-1)}{2}\)，需要的边数 \(tot\) 就是 \(cnt-1+t-2=cnt+t-3\)。

最好的情况肯定是所有点正好用完，也就是 \(cnt=\frac{t \times (t-1)}{2}=n\)。

这时我们可以解得 \(t=\frac{1+\sqrt{1+8n}}{2}\)，推出 \(tot=n+\frac{1+\sqrt{1+8n}}{2}-3\)。

那么我们就可以知道，一个 \(n\) 个点的图简单环长度两两不同，最多有 \(n+\frac{1+\sqrt{1+8n}}{2}-3\) 条边。

那如果边数大于这个值，我们就可以直接输出 Yes 了。

现在我们把边的范围缩小到了 \(n+\sqrt{n}\) 级别。如果我们在图上找到一个 dfs 树，那么非树边就是 \(\sqrt{n}\) 条。

我们可以对这 \(\sqrt{n}\) 条边连的点建虚树，这样我们的点数就到达了 \(\sqrt{n}\) 的级别。

那么这时我们再使用上方的暴力算法就可以达到 \(O(n^2)\) 的优秀复杂度。

那么因为 \(n \le 10^4\)，加上 dfs 根本跑不满，就可以直接通过本题了。

代码实现

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
#define Yes printf("Yes\n")
#define No printf("No\n")
const ll N=1e6+10;
using namespace std;

ll n,m,k;
ll a[N],b[N];//序列
vector<ll>e[N];//图
ll fa[N];//dfs树上的父亲
ll id[N];//在虚树上属于的点的编号
ll dep[N];//深度
ll dis[N];//距离

//虚树
ll tot=1,fir[N],nxt[N],v[N],w[N];
void add_edge(ll x,ll y,ll z){v[++tot]=y;w[tot]=z;nxt[tot]=fir[x];fir[x]=tot;}
void add(ll x,ll y,ll z){add_edge(x,y,z);add_edge(y,x,z);}

void dfs(ll x,ll father){
	fa[x]=father;
	dep[x]=dep[fa[x]]+1;
	ll flag=0;
	//flag=-1表示x是LCA，需要加入虚树
	//flag>0表示x不是LCA，但子树内有点在虚树中
	//flag=0表示x子树内没有点在虚树中
	for(ll y:e[x]){
		if(y==fa[x])continue;
		if(dep[y]){//非树边
			if(dep[x]<dep[y])continue;//保证只连一次
			if(!id[x])id[x]=x;//分配编号
			if(!id[y])id[y]=y;//分配编号
			add(id[x],id[y],1);//连边
			continue;
		}
		dfs(y,x);//递归
		if(id[y]){//y子树在虚树中
			if(flag)flag=-1;//x节点是LCA
			else flag=id[y];//标记y在虚树上的编号
		}
	}
	if(flag==-1&&!id[x])id[x]=x;//分配编号
	if(id[x]){//在虚树中
		for(ll y:e[x]){
			if(fa[y]==x&&id[y]){//是x的儿子且在虚树中
				add(id[x],id[y],dep[id[y]]-dep[id[x]]);//连边
			}
		}
	}else id[x]=flag;
}

ll vis[N];//标记
ll cnt[N];//长度为i的环的个数
bool check(ll x,ll k){//k为标记编号
	if(dep[x]==1)return true;//到达根节点
	vis[x]=k;
	for(ll i=fir[x];i;i=nxt[i]){
		ll y=v[i],z=w[i];
		if(vis[y]==k)continue;
		if(dep[y]>1)continue;//走过的点不走
		if(check(y,k))return true;
	}
	return false;
}

void solve(ll x,ll in){//O(n^4)暴力
	if(!check(x,++k))return;//不能构成环
	for(ll i=fir[x];i;i=nxt[i]){
		ll y=v[i],z=w[i];
		ll t=z+dis[x];//到根节点的距离
		if(i==in)continue;//入边跳过
		if(dep[y]==1){//可以到达根节点
			cnt[t]++;//t就是环长
			if(cnt[t]>2*dep[x]){//长度大于深度的2倍 
				Yes;
				exit(0);
			}
		}
		if(dep[y])continue;
		dep[y]=dep[x]+1;//更新深度
		dis[y]=t;//更新距离
		solve(y,i^1);
		dep[y]=0;//回溯
	}
}

void mian(){
	
	ll ans=0;
	
	scanf("%lld%lld",&n,&m);
	For(i,1,m){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		e[x].pb(y),e[y].pb(x);
	}
	//结论
	if(m>n+(sqrt(1+8*n)+1)/2-3){
		Yes;
		return;
	}
	//建虚树
	For(i,1,n){
		if(!dep[i])dfs(i,0);
	}
	
	For(i,1,n)dep[i]=0;//初始化
	For(i,1,n){
		if(id[i]==i){
			dep[i]=1;
			dis[i]=0;
			solve(i,0);
			dep[i]=0;
		}
	}
	No;
	
}

int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)mian();
	return 0;
}