Codeforce Round 547 Div1. D - Mike and Fish

* Mike and Fish (http://codeforces.com/contest/547/problem/D)

  뭐.. 문제 내용을 보면 생선을 싫어하는 곰, 마이크가 파란 생선과 빨간 생선을 2차원 좌표에 있는 바구니(?)에 하나씩 넣고자 한다. 또한 하나의 x축이나 y축에 대해 파란 생선 개수와 빨간 생선 개수의 차이가 1 이하로 만들기 위해 생선들을 각 좌표에 어떻게 배치시킬 것인지를 묻는 문제다.

[분류 - Eulerian circuit/ Euler circult/ 오일러 회로/ 오일러 서킷] <- Drag하면 보입니당 :P

  아이디어 측면에서 먼저 생각해보자. 각 좌표에 물고기를 하나씩 놓아야하기 때문에 이는 순회를 해야함을 알 수 있다. 순회하는 방법만 정해져 있다면 BLUE, RED, BLUE, RED, BLUE, ... 이런 방식으로 좌표에 물고기를 넣으면 된다(물론 RED 시작이어도 상관없다). 비어 있는 좌표는 있을 수 없다. 그렇다면 순회의 방법론에 대해 생각해보자.

  각 좌표에 대해 서로 영향을 끼치기 위해서는 x좌표 또는 y좌표 둘 중에 하나가 같으면 된다. 문제에서 distinct points라는 표현을 사용했기 때문에 중복되는 점은 존재하지 않는다. 즉, 아래 그림의 경우 세 개의 집합이 생김을 알 수 있다.

  주황색, 파랑색, 초록색에 대해 각각 서로에 대해 연관성을 지니고 있다. 하고 싶은 말은 각 집합에 대해 따로 따로 계산해줘야 한다는 것이다. 가령 주황색 집합이 파랑색 집합에 관여할 수 없으며 그 반대도 마찬가지다.

  이제 하나의 집합에 대해 생각해보자. 같은 집합 내의 서로 다른 좌표에 대해 x좌표 또는 y좌표가 같다면 이 두 좌표는 '강하게' 연결되어 있다. 근시적으로 본다면 가령 (1,1) (1,2) 라는 집합이 있다면 x=1 축에 대해 반드시 서로 다른 물고기를 놓아야 한다. 반대로 (1,1), (2,1)라는 집합이 있다면 y=1 축에 대해 반드시 서로 다른 물고기를 놓아야 한다. 축이 이렇게 좌표에 연관성이 깊으므로 축에 대해 생각해보자. 

  연관성에 대해 생각해본다면 x축과 y축 두 개밖에 없다. 모든 좌표는 이 x축과 y축으로 표현이 가능하다. 즉 이를 이용하여 이분 그래프를 구성한다. 즉, 좌표를 정점이 아닌 간선으로 보는 것이다. (힌트 : n 제한이 2*10^5이기 때문에 절대로 좌표간 관계도를 형성할 수 없다.)

  따라서 좌표 (xi, yi)에 대해 정점 xi에서 정점 yi로 가는 간선이 있다고 그래프를 구성하는 것이다. 하지만 xi와 yi에 대해 서로 구분해야할 필요가 있기 때문에 정점을 구성하는 구문이 필요하다.

  그렇다면 이제 순회를 해야하는데 이 정점들을 순회하려면 어떻게 해야할까? 좌표를 모두 간선으로 바꿨고 모든 간선을 단 한번만 지나야 한다. 이 조건을 만족하는 것은 바로 오일러 회로다. 모든 간선을 단 한 번만 순회하는 사이클을 만드는 것을 통해 하나씩 하나씩 RED, BLUE를 번갈아가며 생선을 놓을 수 있다.

  1. 집합이 모든 정점이 짝수 차수를 가진다면 오일러 회로를 찾을 수 있다. 이 때, 특별히 해야할 작업은 존재하지 않는다.

  2. 홀수 차수를 갖는 정점이 존재한다면 이와 연결된 차수 하나를 제거한다. 제거하는 과정은 홀수 차수를 갖는 정점이 없을 때까지 반복한다. 이 과정이 중요한 이유는 홀수 차수가 몇 개인지 알 수 없기 때문에 오일러 경로를 사용할 수 없기에, 오일러 회로를 만족하는 짝수 차수만을 갖는 집합으로 만들어주기 때문이다.

  지울 때는 반드시 뒷 작업이 필요하다. 하나의 간선에 대해 삭제를 하기 때문에 양 정점에 대해 차수를 줄여주고, 제거함으로써 홀수 차수를 갖는 정점이 생길 수도 있기에 이러한 부분도 고려해야한다. 또 중요한 것은 삭제하는 과정은 마지막 만들어질 짝수 차수 집합에 가장 가까운 간선은 어떤 것일까? 바로 마지막에 삭제한 간선이겠다. 그렇다면 삭제한 간선에 대해 다시 생성하고 RED 또는 BLUE에 대해 값을 대입해야만 한다. 이 속성은 LIFO(Last input first out)이므로 스택을 이용하여 구현하도록 하자.

  +) 짝수 차수 집합에 대해 RED, BLUE 매기는 과정이 끝나고 나면 삭제한 간선이 RED 또는 BLUE 어떤 값이 들어가야하는지는 현재 정점에 RED 혹은 BLUE인 간선이 몇개 연결되어 있는지 확인한다. RED 간선이 BLUE 간선보다 1만큼 많다면 삭제했던 간선을 복구하여 답을 도출할 때는 BLUE로, 아닌 경우엔 RED로 저장하면 되겠다.

- 시간 복잡도 : O((L+n)lg(L+n))

  L : 새로 생성한 정점의 개수(최대 2*10^5)

#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm> 
#include <stack>
using namespace std;
using ll = long long;
const int MAX_V = 400001;
vector<int> adj[MAX_V];
set<pair<int, int>> deleted, used;
map<pair<int, int>, int> pool;
vector<int> c;
bool vi[MAX_V];
void dfs(int u) {
	int x, y;
	vi[u] = 1;
	while (adj[u].size()) {
		int v = adj[u].back();
		adj[u].pop_back();
		x = u % 2 ? v : u;
		y = u % 2 ? u : v;
		auto p = make_pair(x, y);
		if (deleted.find(p) != deleted.end() || used.find(p) != used.end())
			continue;
		used.insert(make_pair(x, y));
		dfs(v);
	}
	c.push_back(u);
}
int main() {
	int n, xi, yi, i, j, x, y, deg[MAX_V] = {}, ans[200001] = {}, clr[MAX_V] = {}, a, b, acc;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xi, &yi);
		xi--, yi--;
		x = 2 * xi, y = 2 * yi + 1;
		adj[x].push_back(y);
		adj[y].push_back(x);
		deg[x]++, deg[y]++;
		pool.insert({ { x,y },i });
	}
	stack<pair<int, int>> stk;
	queue<int> q;
	for (i = 0; i < MAX_V; i++)
		if (deg[i] % 2) q.push(i);
	while (!q.empty()) {
		i = q.front(), q.pop();
		if (deg[i] % 2 == 0) continue;
		do {
			x = i;
			y = adj[i].back();
			adj[i].pop_back();
			if (x % 2) swap(x, y);
		} while (deleted.find({ x,y }) != deleted.end());
		deg[x]--, deg[y]--;
		deleted.insert({ x,y });
		stk.push({ x,y });
		if (deg[x] % 2) q.push(x);
		if (deg[y] % 2) q.push(y);
	}

	for (i = 0; i<MAX_V; i++)
		if (!vi[i] && deg[i]) {
			dfs(i);
			for (j = c.size() - 1, acc = 1; j > 0; j--, acc++) {
				a = c[j], b = c[j - 1]; // a -> b
				clr[a] += (acc % 2 ? 1 : -1), clr[b] += (acc % 2 ? 1 : -1);
				x = a % 2 ? b : a;
				y = a % 2 ? a : b;
				ans[pool[make_pair(x, y)]] = acc;
			}
			c.clear();
		}

	while (!stk.empty()) {
		auto p = stk.top();
		stk.pop();
		x = p.first, y = p.second;
		if (clr[y] > 0 || clr[x] > 0) a = -1;
		else a = 1;
		ans[pool[{x, y}]] = (a == 1 ? 1 : 0);
		clr[x] += a, clr[y] += a;
	}

	for (i = 0; i < n; i++)
		printf("%c", ans[i] % 2 ? 'r' : 'b');

	return 0;
}