CF547D Mike and Fish 题解

CF547D Mike and Fish

题意

• 给定 $n$ 个整点。
• 你要给每个点染成红色或蓝色。
• 要求同一水平线或垂直线上两种颜色的数量最多相差 $1$。
• $n,x_i, y_i \le 2 \times 10^5$。

题解

对于每个点，将横纵坐标之间连一条边。

那么题意转化为对每条边定向使得每个点的入度和出度最多相差 $1$。

由于奇点一定只有偶数个，不妨将其全都连向 $0$。

然后跑一遍欧拉回路即可，时间复杂度 $\mathcal O(n)$。

代码

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;
}