[BAE/<JOON> 문제풀이] 1707. 이분 그래프

핵심::
이분 그래프 개념 문제

풀이::
DFS를 수행하며 탐색되는 정점들에 1, 0을 번갈아 표시한다.

수행이 완료 되기 전에 표시해야할 번호와 정점에 이미 쓰여있는 번호가 겹친다면 이분 그래프가 아니다.

의견::

코드::

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

using namespace std;

int main()
{
	int tc; cin >> tc;	
	while (tc--) {		
		int n, m; cin >> n >> m;
		vector<vector<short>> arr(n + 1);
		for (int i = 1; i <= m; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			arr[a].push_back(b);
			arr[b].push_back(a);
		}
		bool iis = true;
		vector<short> cl(n + 1, -1);
		for (int i = 1; i <= n; i++) {
			if (cl[i] != -1) continue;
			queue<short> q;
			cl[i] = 1;
			q.push(i);
			while (!q.empty()) {
				auto c = q.front(); q.pop();
				bool valid = true;
				for (auto next : arr[c]) {				
					if (cl[next] == cl[c]) {
						valid = false;
						iis = false;
						break;
					}
					if (!valid) break;
					if (cl[next] != -1) continue;
					cl[next] = 1 - cl[c];
					q.push(next);
				}
				if (!iis) break;
			}
			if (!iis) break;
		}
		cout << (iis ? "YES" : "NO") << "\n";
	}

	return 0;
}