染色法判二分图

给出一张由$n$个点，$m$条边组成的无向图。

请你帮忙检查，是否有可能将这$n$个点分成两个集合（集合A和集合B），使得这两个集合满足如下要求：

1.对于某个点$i$，它要么在集合A中，要么在集合B中。并且不会同时在两个集合中。

2.对于某条边$i$，假设它连接的两个点分别为$a$与$b$。要求点$a$和点$b$一个在A集合中，一个在B集合中。（即$a$在集合A，$b$在集合B或$a$在集合B，$b$在集合A）。

满足的话输出Yes，否则输出No。

除此之外，二分图的点数是偶数，并且其所有回路的长度是偶数。

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x3f3f3f3f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
struct bian{
	int next,to,w;
	bian(){
        w=0;
		next=0;
	}
}e[N];
int n,m,head[N],totm,ans,color[N];
void add(int s,int ed,int rm=0){
	e[++totm].next=head[s];
	e[totm].to=ed;
    e[totm].w=rm;
	head[s]=totm;
}
bool dfs(int now){
	for(int i=head[now];i;i=e[i].next){
		int con=e[i].to;
		if(!color[con]){
			color[con]=1-color[now];
			if(!dfs(con)) return 0;
		}
		if(color[con]==color[now]) return 0;
	}
	return 1;
}
int main(){
	n=read(),m=read();
	fs(i,1,m,1){
		int u,v,w;
		u=read(),v=read();
		add(u,v);
		add(v,u);
	}
	totm--;
	if(dfs(1)) puts("Yes");
	else puts("No");
	return 0;
}
/*染色法。
我们给1号节点染上红色，而1的所有邻接点黑，那些邻接点的所有邻接点红……
红是A集合，黑是B几何。
如果有一个点既在A里边又在B里边，那么有问题，这玩意不是二分图。
如果完全没问题，那就OK。
*/