백준 1707번 : 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

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

int color[20001];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int k;
	cin >> k;
	for (int T = 0; T < k; T++) {
		int v, e;
		cin >> v >> e;

		memset(color, 0, sizeof(color));

		vector<int> adj[20001];
		for (int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		queue<int> Q;

		bool flag = true;

		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				color[i] = 1;
				Q.push(i);
	
				while (!Q.empty()) {
					int x = Q.front();
					int cc = color[x];
					Q.pop();

					for (auto nx : adj[x]) {
						if (color[nx] == cc) {
							flag = false;
							cout << "NO\n";
							break;
						}
						else if (color[nx] == 0) {
							color[nx] = cc == 1 ? 2 : 1;
							Q.push(nx);
						}
					}

					if (!flag) break;
				}

				if (!flag) break;
			}
		}


		if (flag) {
			cout << "YES\n";;
		}


	}

	return 0;
}

백준 1707번 이분그래프