BOJ 2889 - 레스토랑 (RESTORAN)

분류 - [ 오일러 회로 ]

  도로를 두 개 이상을 가지는 도시는 반드시 두 레스토랑을 갈 수 있어야 한다. 도로가 없거나 하나 이하의 경우는 생각하지 않기 때문에, 이 명제를 좀 변형 시켜보자.

  "도로를 두 개 이상을 가지는 도시에 대해 두 레스토랑을 보장하기 위해서 A 레스토랑이 있는 도로의 수를 Acnt, B 레스토랑이 있는 도로의 수를 Bcnt라고 할 때, Acnt는 Bcnt와 같아야 한다."

  이것이 의미하는 바는 A와 B 레스토랑의 수를 같게 하면 명확하게 문제에서 원하는 도로를 배치할 수 있다. 따라서 A와 B를 진입/ 진출 간선처럼 생각하고, 항상 진입 간선 수=진출 간선 수가 같은 오일러 회로를 이용하여 문제를 해결한다. 

  단, 여기서 예외처리를 해줘야하는 점이 있다. 우선 Component가 여러 개가 있음을 인지하고~

1) 홀수 도로를 갖는 도시 Component

  이 때 도로에 둘 수 있는 방법은 무조건 존재한다. 홀수 간선을 갖는 도시는 A와 B 중 둘 중 하나를 더 많이 가지게 되는데, 이는 짝수 도시의 상태에 따라 "양보"가 가능하므로 무조건 가능하다. 또한 이 경우엔 오일러 회로를 돌릴 수 없으므로, 오일러 회로를 만족시킬 수 있도록 그래프를 그려준다. 방법은 가짜 도시를 만들어서 홀수 도시와 이어주는 것이다. 오일러 경로를 오일러 회로처럼 쓰기 위해서는 시작점과 끝점을 이어주는 가짜 간선을 만들어주는 것이다. 하지만 여기서는 홀수 도시가 많기 때문에 이를 하나의 가짜 도시에 묶어서  처리해준다.

2) 짝수 도로만을 갖는 도시 Component(이하 짝수 Component)

  짝수 도로만을 가질 때, 경우에 따라 오일러 경로가 존재할 수도 있고, 존재하지 않을 수도 있다.

  아래 그래프의 경우 문제가 요구하는 도시를 절대로 만들 수 없음을 직관적으로 알 수 있다.

  이 현상은 짝수 Component에서 나타날 수 있는데, 도시에 연결된 도로가 각각 2개씩 있을 때 발생할 수 있다. 이는 진입, 진출을 번갈아가면서 A,B 레스토랑을 놓기 때문이다. 또한 간선이 홀수개인 경우에 발생한다(도시에 연결된 도로가 짝수일 뿐이지, 전체적으로 보면 홀수가 될 수 있다). 이는 시작점에 대해 두 개의 간선이 모두 A 또는 B 레스토랑으로 설치되기 때문이다.

  그렇다면 도시에 4개 이상의 도로가 있다면 짝수 Component라도 오일러 회로를 이용하여 문제를 풀 수 있을까? 결론은 풀 수 있다!

  4개 이상의 도로를 가진 도시에 대해 두 도로만 남기고(회로이기 때문에 다시 돌아야니까 두 개의 도로만 남기고~) 나머지를 오일러 회로를 돌렸을 때, 도로에 A 레스토랑만 있었다고 가정하자. 그렇다면 남은 두 도시는 둘 중의 하나는 반드시 B 레스토랑을 설치할 수가 있다(현재 진입, 진출된 도로들은 모두 A 레스토랑이라면 이제 '진출'해야할 도로는 B 레스토랑으로 세울 수 있다).

  2-1) 모든 도시의 차수가 2이고, 그 도로의 수가 홀수일 때는 가능하지 않다.

  2-2) 2-1이 아닌 경우엔 모두 가능하다.

코드 -

#include <cstdio>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
using namespace std;
const int MAX_V = 200001;
struct _e {
	int t;
	list<_e>::iterator rn;
	_e(int t) : t(t) { }
};
void arrange(int& u, int& v) {
	if (u > v) {
		int t = u;
		u = v;
		v = t;
	}
}
list<_e> adj[MAX_V];
void addEdge(int u, int v) {
	adj[u].push_front(_e{ v });
	adj[v].push_front(_e{ u });
	adj[u].begin()->rn = adj[v].begin();
	adj[v].begin()->rn = adj[u].begin();
}

void removeEdge(int u, list<_e>::iterator uv) {
	adj[uv->t].erase(uv->rn);
	adj[u].erase(uv);
}

map<pair<int, int>, int> pool;
int deg[MAX_V] = {}, rt,vcnt;
bool vi[MAX_V];
vector<int> odds;
bool labeling(int u) {
	if (!vi[u]) vcnt++;
	vi[u] = 1;
	if (deg[u] % 2) rt = u, odds.push_back(u);
	if (deg[u] >= 4) rt = u;

	bool ret = 0;
	if (deg[u] != 2) ret = 1;
	for (_e& e : adj[u])
		if (!vi[e.t])
			ret |= labeling(e.t);
	return ret;
}
vector<int> c;
void dfs(int u) {
	vi[u] = 1;
	while (adj[u].size()) {
		auto e = adj[u].begin();
		int v = e->t;
		removeEdge(u, e);
		dfs(v);
	}
	c.push_back(u);
}

int main() {
	int N, E, i, j, u, v, ans[MAX_V] = {}, invalid = 0, fakeVertex, acc, isOddComp;
	scanf("%d%d", &N, &E);
	for (i = 0; i < E; i++) {
		scanf("%d%d", &u, &v);
		u--, v--;
		addEdge(u, v);
		deg[u]++, deg[v]++;
		arrange(u, v);
		pool.insert({ { u,v },i });
	}
	fakeVertex = N + 1;
	for (i = 0; i < N && !invalid; i++)
		if (!vi[i] && deg[i]) {
			rt = i;
			vcnt = 0;
			invalid |= !labeling(i) && vcnt % 2;
			if (!invalid) {
				isOddComp = !odds.empty();
				while (!odds.empty()) {
					addEdge(odds.back(), fakeVertex);
					odds.pop_back();
				}
				if (isOddComp) continue;
				dfs(rt);
				for (j = c.size() - 1, acc = 0; j > 0; j--, acc++) {
					u = c[j], v = c[j - 1];
					if (u == fakeVertex || v == fakeVertex)
						continue;
					arrange(u, v);
					ans[pool[{u, v}]] = acc % 2;
				}
			}
		}
	dfs(fakeVertex);
	for (j = c.size() - 1, acc = 0; j > 0; j--, acc++) {
		u = c[j], v = c[j - 1];
		if (u == fakeVertex || v == fakeVertex)
			continue;
		arrange(u, v);
		ans[pool[{u, v}]] = acc % 2;
	}

	if (invalid) printf("0");
	else {
		for (i = 0; i < E; i++)
			printf("%d\n", ans[i] + 1);
	}
	return 0;
}