취미로 코딩하기

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

이번에 볼 문제는 백준 15511번 문제인 League of Overwatch at Moloco (Hard)이다.
문제는 아래 링크를 확인하자.

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

주어지는 각 직원을 노드, 서로 게임을 같이 해본 적 있는 사람의 쌍을 에지로 하는 그래프 G를 생각하자. 이 때, 문제에서 요구하는 두 집합이 존재하기 위해서는 다음과 같은 두 조건을 만족해야 함을 알 수 있다:

1) G는 이분그래프(bipartite graph)이다.

2) N은 2 이상이다. (각 팀에는 최소한 한 명의 인원이 필요하기 때문이다.)

따라서 G가 이분그래프인지를 판단하는 것으로 문제를 해결할 수 있다. 이는 BFS 또는 DFS를 이용해 간단히 판단할 수 있다. 어떤 그래프가 이분그래프일 동치조건 중 "홀수 길이의 사이클이 존재하지 않는다"는 동치명제를 이용하자.

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

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

int N, M;
vector<int> G[1000001];
int dist[1000001];
bool chk = 1;

void dfs(int cur) {
	for (auto& x : G[cur]) {
		if (dist[x]) {
			if (((dist[cur] + dist[x]) & 1) == 0) chk = 0;
		}
		else {
			dist[x] = dist[cur] + 1;
			dfs(x);
		}
	}
}

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

	cin >> N >> M;
	if (N == 1) {
		cout << "IMPOSSIBLE";
		return 0;
	}

	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (dist[i]) continue;
		dist[i] = 1;
		dfs(i);
	}

	if (chk) cout << "POSSIBLE";
	else cout << "IMPOSSIBLE";
}