! BJOI2018染色

首先有奇环肯定不行

手算一下发现下列两种不行：

不行的：

奇环
形成3个及以上的环((m>n+1))
(m=n+1)即两个偶环相交是相交的两个点之间的三条链不满足(2+2+偶数)

详解

用(dfs)+拓扑排序判一下即可

这个图有点特殊，咋一看出来是3个环，还以为是YES，但按上述可以卡掉，实际上是这样：

与第一类不符合的图形等价

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=10004;
int n,m,fl,P,E,col[N],in[N];
vector<int>e[N],s;
queue<int>q;
void dfs(int x,int c){
	if(!fl)return;
	col[x]=c;P++;E+=e[x].size();
	s.push_back(x);
	for(auto v:e[x]){
		if(col[v]==c){fl=0;return;}
		if(col[v]==-1)dfs(v,c^1);
	}
}
inline void solve(){
	n=read();m=read();
	fl=1;
	memset(col,-1,sizeof(col));
	for(int i=1;i<=n;i++)e[i].clear();
	for(int i=1,u,v;i<=m;i++){
		u=read();v=read();
		e[u].push_back(v);e[v].push_back(u);
	}
	for(int i=1,tmp,res;i<=n;i++)if(col[i]==-1){
		s.clear();P=E=0;
		dfs(i,0);
		if(!fl)break;
		if(E/2>P+1){fl=0;break;}//1-2 2-3 3-4 4-1 1-5 5-2 1-6 6-2 4-7 7-3 4-8 8-3
		if(E/2<=P)continue;
		for(auto v:s){
			in[v]=e[v].size();
			if(in[v]==1)q.push(v);
		}
		while(!q.empty()){
			int x=q.front();q.pop();
			for(auto v:e[x])
				if((--in[v])==1)q.push(v);
		}
		tmp=0;
		for(auto u:s)if(in[u]==2){
			res=0;
			for(auto v:e[u])if(in[v]==3)res++;
			if(res==2)tmp++;
		}
		if(tmp<2){fl=0;break;}
	}
	if(fl)puts("YES");
	else puts("NO");
}
int main(){
	int T=read();
	while(T--)solve();
	return (0-0);
}