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

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

1707번: 이분 그래프

 

---

풀이

- BFS 사용, 레벨 별로 다른 값을 visited 배열에 저장하여 이분 그래프를 구분.- 같은 레벨의 노드끼리 값이 다를 수 있으므로 방문 여부와 상관 없이 모든 노드에서 탐색이 필요  (이 때, 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;
}