이분 그래프 (feat. 백준, 1707번)

이분 그래프
https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <set>
#include <map>
using namespace std;
int K, V, E;
map<int, set<int>> arr;
int ans[20001];
bool solution(register int x) {
	queue<int> q;
	q.push(x);
	ans[x] = 1;
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		for (auto iter = arr[v].begin(); iter != arr[v].end(); ++iter) {
			if (ans[*iter] == 0)
				ans[*iter] = -ans[v], q.push(*iter);
			else
				if (ans[*iter] == ans[v])
					return false;
		}
	}
	for (register int i = 1; i <= V; ++i)
		if (ans[i] == 0)
			return solution(i);
	return true;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> K;
	for (register int k = 0, e, x, y; k < K; ++k) {
		cin >> V >> E;
		arr.clear();
		memset(ans, 0, sizeof(ans[0]) * (V + 1));
		for (e = 0; e < E; ++e)
			cin >> x >> y, arr[x].insert(y), arr[y].insert(x);
		if (solution(1))
			cout << "YES" << "\n";
		else
			cout << "NO" << "\n";
	}
	return 0;
}
// *&)*@*

1. 다른 풀이 방법들과는 다르게 풀어보았습니다.
2. V값이 주어지면 1~V까지의 노드(정점)은 무조건 존재하게 됩니다.
3. 처음 노드는 항상 1로 시작합니다. 왜냐하면 1부터 V까지의 노드가 존재하기 때문입니다.
4. 첫 노드는 항상 배열에 1을 삽입합니다. 그리고 시작 노드와 연결되는 끝 노드는 0이라면 항상 -(시작 노드) 의 값을 삽입합니다.
5. 만약 끝 노드가 0이 아니라면 시작 노드와 끝 노드는 달라야만 합니다. 만약 같으면 이분 그래프가 아닙니다.
6. 1~V까지의 노드중에 0이 있다면 아직 해당 노드를 검사하지 않은 것이므로 3번부터 해당 노드를 수행합니다.