题解 | 【模板】二分图结构Ⅰ-A ‖ 染色判定：DFS

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10;

struct Edge{
	int u,v;
	int next;
}edge[N*2];

int n,m,head[N],cnt;
int color[N];

void add(int u,int v){
	edge[++cnt].next=head[u];
	edge[cnt].u=u;
	edge[cnt].v=v;
	head[u]=cnt;
	return;
}

void bfs(int x){
	
	queue<int> q;
	bool f=false;
	color[x]=1;
	q.push(x);
	
	while(!q.empty()){
		int st=q.front();q.pop();
		
		for(int i=head[st];i!=0;i=edge[i].next){
			int to=edge[i].v;
			if(color[st]==1){
				if(color[to]==0){
					color[to]=2;
					q.push(to);
				}else if(color[to]==1){
					cout<<"NO"<<endl;
					return;
				}
			}else{
				if(color[to]==0){
					color[to]=1;
					q.push(to);
				}else if(color[to]==2){
					cout<<"NO"<<endl;
					return;
				}
			}
		}
	}
	
	cout<<"YES"<<endl;
	
	return;
}

void solve(){
	
	bfs(1);
	
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	
	solve();
	
    return 0;
}