1, Title

Click here to see the question

2, Solution

thank you This big guy My blog is really good.

When we do it, we will not even be able to perform a violent search. Let's first examine a promising violent search.

First enumerate the starting point, and then try to find a circuit to the starting point (the most violent method is to enumerate the next point and then backtrack). When finding each point, judge that if it is not possible to form a ring (that is, it does not reach the starting point through the node in the search stack), then exit directly.

Analyze the time complexity of this method. First, according to the drawer principle, the number of rings does not exceed \ (n\), and the worst case is that \ (3\sim n\) is distributed one each. Considering that a ring with a length of \ (i\) will be searched \ (2i\) times, each time \ (i\) points need to be taken, so it is \ (\sum\i=3}^n2i^2=o (n^3) \); At this point, multiply by the complexity of the check, and we get a stable \ (O(n^4) \) algorithm. With a little randomization and pinching the watch, you can casually cross the first four bags, and even directly cross the topic.

There is a fairy conclusion that \ (m>n+2\sqrt n\) has no solution. Consider randomly deleting \ (\sqrt n\) edges, and expect the number of rings left:

Then there must be a kind of edge deletion to make the number of remaining rings \ (\leq \sqrt n\), and we can delete all rings with \ (\sqrt n\) times. In other words, we can use \ (2\sqrt n\) times to make the graph have at most \ (n-1\) edges, so the number of edges of the original graph must not exceed \ (n+2\sqrt n\)

Considering a \ (\tt dfs\) tree of the original graph, we mark the non tree edges as key points, then establish a virtual tree of key points, and then add the non tree edges to get a graph with the number of points and edges at the \ (O(\sqrt n) \) level. Finding a ring on this graph is equivalent to finding a ring on the original graph. The \ (O(n^4) \) method introduced at the beginning can support finding a ring with a weighted edge. Apply it directly, with time complexity \ (O(n^2) \)

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
const int M = 10005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,tot=1,f[M],zz[M];vector<int> g[M];
int p[M],vis[M],dep[M],dis[M],len[M],cnt[M];
struct edge{int v,c,next;}e[M<<1];
void add(int u,int v,int c)
{
	e[++tot]=edge{v,c,f[u]},f[u]=tot;
	e[++tot]=edge{u,c,f[v]},f[v]=tot;
}
void dfs(int u,int fa)
{
	int son=0;
	dep[u]=dep[fa]+1;zz[u]=fa;
	for(int v:g[u])
	{
		if(v==fa) continue;
		if(dep[v])
		{
			if(dep[u]<dep[v]) continue;
			if(!p[u]) p[u]=u;
			if(!p[v]) p[v]=v;
			add(p[u],p[v],1);
			continue;
		}
		dfs(v,u);
		if(p[v]) son=son?-1:p[v];
	}
	if(!p[u] && son<0) p[u]=u;
	if(p[u])
	{
		for(int v:g[u]) if(zz[v]==u && p[v])
			add(p[u],p[v],dep[p[v]]-dep[p[u]]);
	}
	else p[u]=son;
}
int check(int u,int nw)
{
	if(!dep[u]) return 1;vis[u]=nw;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(vis[v]==nw || dep[v]>0) continue;
		if(check(v,nw)) return 1;
	}
	return 0;
}
void work(int u,int fa)
{
	if(!check(u,++k)) return ;
	for(int i=f[u];i;i=e[i].next)
	{
		int v=e[i].v,c=e[i].c,r=c+dis[u];
		if(i==fa) continue;
		if(!dep[v])//find root
		{
			if(!len[r]) len[r]=dep[u]+1;
			if(len[r]!=dep[u]+1) {puts("Yes");exit(0);}
			cnt[r]++;
			if(cnt[r]>2*len[r]) {puts("Yes");exit(0);}
		}
		if(dep[v]>=0) continue;
		dep[v]=dep[u]+1;dis[v]=r;
		work(v,i^1);dep[v]=-1;
	}
}
signed main()
{
	n=read();m=read();
	if(m>n+2*sqrt(n)) {puts("Yes");return 0;}
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		if(!dep[i]) dfs(i,0);
	for(int i=1;i<=n;i++) dep[i]=-1;
	for(int i=1;i<=n;i++) if(p[i]==i)
		dep[i]=dis[i]=0,work(i,0),dep[i]=-1;
	puts("No");
}