[백준][1707][C++] 이분 그래프

링크

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

1707번: 이분 그래프

해설

해설에 앞서 이분 그래프란?

인접한 vertex의 색이 모두 다르게 칠하는데 단 2가지 색으로만 칠할 수 있는 그래프를 말합니다.

한마디로 특정 버텍스에서 어떤 곳으로 든 이동시 퐁 당 퐁 당 이 되어야 한다는 뜻입니다.

 

핵심은 BFS를 이용하는 것입니다.

위의 설명대로 퐁 당 퐁 당 이 되어야 하기 때문에 BFS로 탐색 시 임의 값 0, 1 이 번갈아 나오면 됩니다.

 

알고리즘을 정리하면

1. BFS 를 실시하는데 연결된 모든 vertex의 value는 현재 vertex의 value와 다른 값이 되어야 한다.

2. 모든 vertex에 대해 BFS를 실시하였음에도 불구하고 모두 만족하면 YES 아니면 NO

 

아래 코드에 모두 구현되어있다.

 

코드의 경우 방문하지 않은 곳은 -1  방문할 경우 각 위치에 맞는 value 인 0 or 1 이 들어가게 된다.

vertex 방문 시 항상 인접한 모든 vertex를 검사해서 내 value와 다른지 확인한다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int K, V, E;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> K;

	for (int i = 0; i < K; ++i) {
		cin >> V >> E;
		vector <vector <int>> v(V, vector<int>());
		vector <int> table(V, -1);
		for (int j = 0; j < E; ++j) {
			int a, b;
			cin >> a >> b;
			a--; b--;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		queue <pair <int, int>> que;
		que.push({ 0, 0 });
		while (true) {
			while (!que.empty()) {
				int vtx = que.front().first, value = que.front().second;
				if (table[vtx] != -1) {
					if (table[vtx] != value)
						break;
					else {
						que.pop();
						continue;
					}
				}
				que.pop();
				table[vtx] = value;
				value = value == 0 ? 1 : 0;
				for (int j = 0; j < v[vtx].size(); ++j)
					que.push({ v[vtx][j] , value });
			}
			if (!que.empty()) {
				cout << "NO" << "\n";
				break;
			}
			else {
				int i = 0;
				for (; i < V; ++i) {
					if (table[i] == -1)
						break;
				}
				if (i == V) {
					cout << "YES" << "\n";
					break;
				}
				que.push({ i, 0 });
				
			}
		}
		
	}

	return 0;
}