취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1707번 문제인 이분 그래프이다.
문제는 아래 링크를 확인하자.

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

이 문제는 주어진 그래프가 이분 그래프인지를 판단하는 문제이다.

이분그래프의 판단은 그래프를 인접한 두 노드의 색이 다른 색으로 칠해지게 색칠할 수 있는지 판단하는 것과 같으므로, 두 가지 색으로 색칠하며 그래프를 탐색하는 것으로 문제를 해결할 수 있다.

주어진 그래프가 연결그래프라는 보장이 없다는 점에 유의하자.

아래는 제출한 소스코드이다.

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

vector<int> G[20001];
int visited[20001];
queue<int> que;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		memset(visited, 0, sizeof(visited));
		bool chk = 1;

		int V, E; cin >> V >> E;
		for (int i = 1; i <= V; i++) G[i].clear();
		while (E--) {
			int x, y; cin >> x >> y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
		for (int i = 1; i <= V; i++) {
			if (visited[i]) continue;
			visited[i] = 1;
			que.push(i);
			while (!que.empty()) {
				int current = que.front(); que.pop();
				int partition = visited[current];
				if (partition == 1) {
					for (auto node : G[current]) {
						if (visited[node] == 0) {
							visited[node] = 2;
							que.push(node);
						}
						else if (visited[node] == 1) chk = 0;
					}
				}
				else {
					for (auto node : G[current]) {
						if (visited[node] == 0) {
							visited[node] = 1;
							que.push(node);
						}
						else if (visited[node] == 2) chk = 0;
					}
				}
			}
		}
		if (chk) cout << "YES\n";
		else cout << "NO\n";
	}
}