BOJ(C/C++) No. 1707: 이분 그래프

설명

– BFS를 사용하여 이분 그래프를 구별하기 위해 방문 배열에 레벨별로 다른 값을 저장합니다.– 동일한 레벨의 노드는 다른 값을 가질 수 있으므로 방문 여부와 상관없이 모든 노드를 검색해야 합니다. (이때 Q.push()는 방문하지 않은 노드에서만 수행되므로 이미 방문한 노드에 대한 검색은 한 수준 아래만 검색합니다.)

암호

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

vector <int> G(20001);
int visited(20001);

bool BFS(int start) {
	queue <int> Q;
	int now, color;

	// 방문하지 않은 노드라면 값을 1로 지정 -> 모든 노드가 같은 트리에 속해있지 않은 경우
	if (!visited(start)) visited(start) = 1;
	Q.push(start);

	while (!Q.empty()) {

		now = Q.front();
		color = visited(now); // 해당 노드의 값 저장
		Q.pop();

		for (int i : G(now)) {

			// 방문하지 않은 노드의 경우 현재 레벨과 다른 값 저장
			if (!visited(i)) {
				if (color == 1) visited(i) = -1;
				else if (color == -1) visited(i) = 1;
				Q.push(i);
			}

			// 방문한 노드일 경우 현재 레벨과 같은 값일 경우 이분 그래프가 아니므로 중단 후 false 값 리턴
			else {
				if (color == visited(i)) return false;
			}
		}
	}
	return true;
}
bool Is_Bip(int N) {
	// 방문 여부와 상관 없이 모든 노드를 탐색
	for (int i = 1; i <= N; i++) {
		if (!BFS(i)) return false;
	}
	return true;
}
int main() {
	int K, V, E, a, b;
	scanf("%d", &K);
	for (int k = 0; k < K; k++) {

		// input
		scanf("%d %d", &V, &E);

		for (int i = 0; i < E; i++) {
			scanf("%d %d", &a, &b);
			G(a).push_back(b);
			G(b).push_back(a);
		}

		// bfs
		if (Is_Bip(V)) printf("YES\n");
		else printf("NO\n");

		// init
		fill(visited, visited + V + 1, false);
		for (int i = 1; i <= V; i++) G(i).clear();

	}
	return 0;
}