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 + 20; 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 = 1; 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 = 1; i <= n; ++i) { add(2 * i - 1, 2 * i); add(2 * i, 2 * i - 1); } for (int i = 1; i <= 2 * n; ++i) { if (vis[i]) continue; vis[i] = true; dfs(i, 0); } for (int i = 1; i <= n; ++i) { printf("%d %d ", col[b[i]] + 1, col[g[i]] + 1); } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }