二分图匹配 + 构造 E. Arpa’s overnight party and Mehrdad’s silent entering

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

跪着看题解后才会的。

对于任何一对BF[i]和GF[i]

连接了一条边后，那么他们和隔壁都是不会有边相连的了，这是题目数据保证的。因为BF[i]和GF[i]是唯一确定的嘛。

那么，我们把BF[i]连接去GF[i]的边叫1类边。

然后把2 * i - 1 和 2 * i也连上边，是第二类边。

那么每个顶点的度数都是2，并且都是一条第一类边和一条第二类的。

那么如果有环，也是偶数环，不存在几圈。所以直接染色即可。

hack:这个二分图可能不是全部连接好的（就是有多个连通分量）。其实本来就不应该认为一定只有一个连通分量。所以需要每个点都枚举一次

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn = 1e6 + ;

int first[maxn];

struct node {

    int tonext;

    int u, v;

}e[maxn];

int num;

int g[maxn];

int b[maxn];

int col[maxn];

void add(int u, int v) {

    ++num;

    e[num].u = u;

    e[num].v = v;

    e[num].tonext = first[u];

    first[u] = num;

}

bool vis[maxn];

int must[maxn];

void dfs(int cur, int which) {

    col[cur] = which;

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

        if (vis[v]) {

//            if (col[v] != !which) {

//                cout << -1 << endl;

//                exit(0);

//            }

            continue;

        }

        vis[v] = true;

        dfs(v, !which);

    }

}

void work() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; ++i) {

        int u, v;

        scanf("%d%d", &u, &v);

        b[i] = u;

        g[i] = v;

        add(u, v);

        add(v, u);

    }

    for (int i = ; i <= n; ++i) {

        add( * i - ,  * i);

        add( * i,  * i - );

    }

    for (int i = ; i <=  * n; ++i) {

        if (vis[i]) continue;

        vis[i] = true;

        dfs(i, );

    }

    for (int i = ; i <= n; ++i) {

        printf("%d %d\n", col[b[i]] + , col[g[i]] + );

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}