CF547D Mike and Fish

将一个点 \((x,y)\) 定义为 \(x\) 向 \(y\) 连的一条无向边，将问题转化为求欧拉路径，这样入度减出度必然 \(\leq 1\)，这样还是不太好做，再转化一步，将每个点向一个虚拟点连一条边，那么我们就可以发现这样做只需要跑一个欧拉回路即可，因为度数为奇数的点也即欧拉路径的起点和终点一定是偶数个。
代码实现如下

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
using namespace std;
template <typename T> void read(T &n){ bool f = 1; char ch = getchar(); n = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0; for (; isdigit(ch); ch = getchar()) n = (n << 1) + (n << 3) + (ch ^ 48); if (f == 0) n = -n;}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 4e5 + 10;
int n;
int head[N], cnt = 1, flg[N << 1], ans[N], deg[N], tag;
struct edge{
	int id, v, nxt;
}e[N << 1];

inline void aedge(int id, int u, int v) {
	e[++cnt] = (edge) {id, v, head[u]}; head[u] = cnt;
}

inline void dfs(int u) {
	for (int &i = head[u]; i; i = e[i].nxt) {
		if (flg[i]) continue ;
		flg[i] = flg[i ^ 1] = 1;
		ans[e[i].id] = tag;
		tag ^= 1;
		dfs(e[i].v);
		
	}
}

int main(){
	//FO("");
	read(n);
	U(i, 1, n) {
		int u, v;
		read(u), read(v);
		v += 2e5;
		deg[u]++, deg[v]++;
		aedge(i, u, v), aedge(i, v, u);
	}

	U(i, 1, N - 10) if (deg[i] & 1) aedge(0, i, 0), aedge(0, 0, i);
	U(i, 0, N - 10) dfs(i);
	U(i, 1, n) if (ans[i]) putchar('b'); else putchar('r');
	return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16852857.html