题解 CF547D 【Mike and Fish】
xht
2019-12-07 23:48:29
> [CF547D Mike and Fish](https://codeforc.es/contest/547/problem/D)
## 题意
- 给定 $n$ 个整点。
- 你要给每个点染成红色或蓝色。
- 要求同一水平线或垂直线上两种颜色的数量最多相差 $1$。
- $n,x_i, y_i \le 2 \times 10^5$。
## 题解
对于每个点，将横纵坐标之间连一条边。
那么题意转化为对每条边定向使得每个点的入度和出度最多相差 $1$。
由于奇点一定只有偶数个，不妨将其全都连向 $0$。
然后跑一遍欧拉回路即可，时间复杂度 $\mathcal O(n)$。
## 代码
```cpp
const int N = 2e5 + 7;
int n, v[N<<1], d[N<<1], h[N<<1], e[N<<2], t[N<<2], c = 1;
inline void add(int x, int y, int z = 1) {
e[++c] = y, t[c] = h[x], h[x] = c;
if (z) add(y, x, 0);
}
void dfs(int x) {
for (int &i = h[x]; i; i = t[i])
if (!v[i>>1]) v[i>>1] = 1 + (x < N), dfs(e[i]);
}
int main() {
rd(n);
for (int i = 1, x, y; i <= n; i++)
rd(x), rd(y), add(x, y + N), ++d[x], ++d[y+N];
for (int i = 1; i < N << 1; i++)
if (d[i] & 1) add(0, i);
for (int i = 1; i < N; i++) dfs(i);
for (int i = 1; i <= n; i++) putchar("br"[v[i]-1]);
return 0;
}
```