BOJ 26032 Icy Itinerary

문제 링크입니다.

문제 요약

$N$개의 정점과 $M$개의 빨간 간선, ${N(N-1) \over 2}-M$개의 파란 간선이 있습니다.

$N$개의 정점을 적당한 순서로 나열합니다. (첫 정점은 $1$번으로 고정입니다.) 나열된 순서 상에서 인접한 정점들 사이를 잇는 간선만 고려했을 때, 같은 색의 간선끼리는 모두 이어져 있도록 정점을 나열하는 방법을 찾으세요.

풀이

풀이 이해에 도움이 되는 영상입니다. 사실 풀이의 한 80%쯤이 영상에 있습니다.

1번부터 $i$번 정점까지 적당히 잘 나열했다고 치겠습니다. 그러면 두 간선의 색이 바뀌는 정점이 최대 1개 있습니다. 이 정점을 $x$번 정점이라고 합시다. 없다면 마지막 정점을 그러한 정점으로 취급해 줍시다.

여기에 $(i+1)$번 정점을 추가하면서 원래의 규칙을 유지할 수 있으면 됩니다. WLOG 왼쪽이 빨간 간선, 오른쪽이 파란 간선이라고 해보겠습니다. 만약 $x$번 정점과 $(i+1)$번째 정점을 잇는 간선이 파랗다면, $(i+1)$번 정점을 왼쪽으로 꽂아넣으면 됩니다. 반대로 두 정점을 잇는 간선이 빨갛다면, $(i+1)$번 정점을 오른쪽으로 꽂아넣으면, 항상 규칙을 만족하면서 정점을 추가할 수 있습니다.

$N \le 2$ 일 때는 당연히 가능하므로, 수학적 귀납법에 의해 이러한 방법이 $N, M$의 값에 관계없이 항상 성립함을 알 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
set<int> e[303030];

int prv[303030], nxt[303030];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m; while(m--){
		int u, v; cin >> u >> v; e[u].insert(v); e[v].insert(u);
	}
	for(int i = 1; i <= n; i++){
		e[0].insert(i);
		e[i].insert(0);
	}
	nxt[0] = 1; nxt[1] = n+1;
	prv[n+1] = 1; prv[1] = 0;
	int mid = 1;
	for(int i = 2; i <= n; i++){
		if(e[mid].count(i)){
			//cout << "y ";
			prv[i] = mid;
			nxt[i] = nxt[mid];
			prv[nxt[mid]] = i;
			nxt[mid] = i;
			if(e[i].count(nxt[i])) mid = nxt[i];
			else mid = i;
		}
		else{
			//cout << "n ";
			prv[i] = prv[mid];
			nxt[i] = mid;
			nxt[prv[mid]] = i;
			prv[mid] = i;
			if(e[i].count(prv[i])) mid = i;
			else mid = prv[i];
		}
		if(mid == 1){
			//cout << "swap ";
			if(prv[1] == 0){
				mid = prv[n+1];
				swap(nxt[mid], prv[1]);
				nxt[n+1] = 1;
				prv[0] = mid;
			}
			else{
				mid = nxt[0];
				swap(prv[mid], nxt[1]);
				nxt[n+1] = mid;
				prv[0] = 1;
			}
			swap(prv, nxt);
		}
	}
	
	if(nxt[0] == 1) for(int i = 1, now = 0; i <= n; i++){
		cout << nxt[now] << ' '; now = nxt[now];
	}
	else for(int i = 1, now = n+1; i <= n; i++){
		cout << prv[now] << ' '; now = prv[now];
	}
}