题解 | 二分图判定

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main () {
	int n, m;
	cin >> n >> m;
	vector<vector<int> > graph(n + 1);
	vector<int> color(n, -1);
	int v1, v2;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	queue<int> q;
	bool ans = true;
	for (int i = 1; i <= n; i++) {
		if (color[i] < 0) {
			q.push(i);
			color[i] = 0;
			while (!q.empty()) {
				int v = q.front();
				q.pop();
				for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++) {
					int to = *it; 
					if (color[to] < 0) {
						color[to] = color[v] ^ 1;
						q.push(to);
					} else if (!(color[to] ^ color[v])) {
						ans = false;
						break;	
					}
				} 
			}
 		}
 		if (!ans) break;
 	}
 	cout << (ans ? "Yes" : "No") << endl;
}