题目
网上那个啥dfs的垃圾做法随便弄组数据已经hack掉了
做法
纯奇环偶环通过dfs树上，染色判断（由于偶环可能有两个奇环，通过一点相交，dfs树上并不能判完）
两环如果相交必定形成偶环，由于不可以重复经过边，把每个边双提出来判断一下是否存在两个环以上即可
Code
为增加代码的可读性写得比较冗长
#include<bits/stdc++.h>
typedef int LL;
const LL maxn=1e6+9;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}return x*f;
}
struct node{
LL to,nxt;
}dis[maxn];
LL n,num,odd,even,tot1,tot2,tim,m,T;
LL head[maxn],cir[maxn],col[maxn],dfn[maxn],low[maxn],visit[maxn];
inline void Add(LL u,LL v){
dis[++num]=(node){v,head[u]}; head[u]=num;
}
void Dfs1(LL u,LL ff){
for(LL i=head[u];i!=-1;i=dis[i].nxt){
LL v(dis[i].to);if(v==ff) continue;
if(!col[v]){
col[v]=3-col[u]; Dfs1(v,u);
}else{
if(col[v]==col[u]) odd=true;
else even=true;
}
}
}
void Dfs2(LL u,LL ff){
dfn[u]=low[u]=++tim;
for(LL i=head[u];i!=-1;i=dis[i].nxt){
LL v(dis[i].to); if(v==ff) continue;
if(!dfn[v]){
Dfs2(v,u); low[u]=std::min(low[v],low[u]);
if(low[v]>dfn[u]){
cir[i]=cir[i^1]=true;
}
}else low[u]=std::min(low[u],dfn[v]);
}
}
void Dfs3(LL u,LL ff){
++tot1; visit[u]=true;
for(LL i=head[u];i!=-1;i=dis[i].nxt){
if(cir[i]) continue;
LL v(dis[i].to); tot2++;
if(v==ff || visit[v]) continue;
Dfs3(v,u);
}
}
int main(){
T=Read();
while(scanf("%d%d",&n,&m)==2){
num=-1;
for(LL i=1;i<=n;++i) head[i]=-1;
for(LL i=1;i<=n;++i) visit[i]=col[i]=dfn[i]=low[i]=0;
for(LL i=0;i<=(m<<1);++i) cir[i]=0;
odd=even=tim=0;
for(LL i=1;i<=m;++i){
LL u(Read()),v(Read());
Add(u,v); Add(v,u);
}
for(LL i=1;i<=m;++i){
if(!dfn[i]) col[i]=1,Dfs1(i,0),Dfs2(i,0);
}
for(LL i=1;i<=n;++i){
if(!visit[i]){
tot1=tot2=0;
Dfs3(i,0);
tot2>>=1;
if(tot1!=1){
if(tot2>tot1) even=true;
}
}
}
if(odd) puts("YES");else puts("NO");
if(even) puts("YES"); else puts("NO");
}
}