Codeforces Round #383 (Div. 2) E. Arpa’s overnight party and Mehrdad’s silent entering

http://codeforces.com/contest/742/problem/E

N쌍의 커플이 있고 이들이 원형 탁자에 앉아 있다.

이 2N 명의 사람들에게 1번음식 또는 2번음식을 주어야 한다. 단 조건이 있다.

1. 커플은 서로 다른 음식을 먹어야한다.

2. 탁자에서 연속된 세 사람이 같은 음식을 먹으면 안된다.

주어진 조건을 만족하는 조합이 있으면 그것을 출력하고 없으면 -1을 출력하는 문제이다.

우선 0번 ~ 2N-1번 사람들에 대해

2i번 사람과 2i+1번 사람을 간선으로 이어보자. 그리고 커플끼리 간선으로 이어보자.

이분 그래프에서 특정 노드에 대해 인접한 노드들은 모두 색이 다르므로

만약 이렇게 했을 때의 그래프가 이분 그래프라면 주어진 두 조건을 만족할 것이다.

그런데 이렇게 하면 무조건 이분 그래프라는 것을 증명할 수가 있다.

우선 2i번 사람과 2i+1번 사람끼리 이어줬을 때 2i번 사람과 2i+1번 사람을 하나의 덩어리라고 보고

이 덩어리들을 위에서부터 쭉 나열해보자.

그럼 현재 왼쪽을 1번 음식, 오른쪽을 2번 음식이라고 보면

이분 그래프가 만들어진다. 이제 커플 관계를 나타내는 간선을 만들어 줘야 하기 때문에

각각의 사람은 딱 한명의 추가적인 사람과 이어져야 한다.

서로 같은 덩어리 끼리 커플이라면 이분 그래프가 유지되는것은 자명하다.

그럼 서로 다른 덩어리 끼리 커플이라 이어줄 때, 같은 음식끼리 이어줬을 경우에는 한쪽을 좌우 반전시켜주면

이분 그래프가 유지된다. 이것을 계속 반복하다보면 마지막 남은 두 덩어리의 남은 노드는 서로 다른 음식이기 때문에

결과적으로 이분 그래프가 된다는 것을 알 수가 있다.

 

그렇다면 불가능한 경우는 없고, 그냥 저렇게 그래프를 만들어 준뒤 그래프 색칠하기를 하면 답이다.

그리고 이분 그래프란 '길이가 홀수인 사이클이 없는 그래프' 라고 말할 수도 있는데

저렇게 그래프를 구성했을 경우 다른 덩어리의 노드로 이동한 경우

왔던 간선으로 다시 가지 않는 이상 무조건 같은 덩어리의 다른 노드로

이동해야 또 다른 덩어리로 갈 수가 있기 때문에 홀수인 사이클이 없다고도 볼 수 있기 때문에 이분 그래프가 된다.

 

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int N;
vector<int> G[200003];
int ans[200003];
pair<int, int> in[100003];
void dfs(int cur, int col){
    if(ans[cur]) return;
    ans[cur] = col;
    for(int next : G[cur]) dfs(next, 3 - col);
}
int main() {
    fastio();
    cin >> N;
    for(int i = 0 ; i < N; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        in[i] = {a, b};
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i = 0 ; i < 2 * N; i+=2){
        G[i].push_back(i + 1);
        G[i + 1].push_back(i);
    }
    for(int i = 0 ; i < 2 * N; i++) dfs(i, 1);
    for(int i = 0 ; i < N; i++){
        cout << ans[in[i].first] << " " << ans[in[i].second] << "\n";
    }
    return 0;
}