#include<bits/stdc++.h>
using namespace std;
int vis[100007];
vector<int>v[100007];
vector<int>vt;
int deg[100007];
void dfs(int a,int nev){//dfs判环
for(auto&x:v[a]){
if(!vis[x]&&x!=nev){//如果有不经过另一个度数为4的环,则图中定有三个环
vis[x]=1;
dfs(x,nev);
}
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int a=0,b=0;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
deg[a]++;
deg[b]++;
}
int flag=0;
for(int i=1;i<=n;i++){
if(deg[i]%2==1){//不是欧拉图直接否定
printf("No");
return 0;
}
if(deg[i]>=6)//度数大于等于6一定有三个环
flag=1;
if(deg[i]>=4)//分类讨论
vt.push_back(i);
}
if(flag){
printf("Yes");
return 0;
}
else{
if(vt.size()==2){//如果两个为度数为4的点之间有环
dfs(vt[0],vt[1]);
if(vis[vt[0]]){//有环
printf("Yes");
return 0;
}
}
else if(vt.size()>2){//图中有两个以上度数为4的点图中必定有三个环
printf("Yes");
return 0;
}
}
printf("No");
return 0;
}
Atcoder Grand Contest 032C(欧拉回路,DFS判环)
保持热爱 不懈努力
不试试看怎么知道会失败呢(划掉)
世上无难事 只要肯放弃(划掉)