1 条题解
-
0
yb 的题解 Qwq。
CF741C 题解
有 个人按给定顺序排成环，这 个人构成了 对情侣。
构造一种方案，给每个人一个值 或 ，使得任意两个情侣的值不同，任意相邻的 个人值不同（即有一个人与另外两个人值不同）。
。
奇妙的构造方法：我们对于所有情侣和点对 ， 连边跑二分图染色即可，我们可以证明这个算法正确，接下来称情侣之间的边为情侣边， 与 之间的边为朋友边（雾）。
- 首先证明构造出的方案正确，情侣之间显然不同，相邻的 个人之间显然有一条朋友边，因此满足题目要求；
- 接着需要证明肯定能构造出一种方案。我们知道一个图是二分图有一个充要条件：不存在奇环。假设存在一个环，因为一个点只连了一条情侣边和朋友边，所以环上情侣边和朋友边一定是交替出现的。又因为是环，所以情侣边与朋友边数量相等（联想小学的环上种树题目），因此环一定是偶环。
时间复杂度 。
CODE
#include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 0; char c = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } #define N 200010 #define pb push_back int n, x[N], y[N], c[N]; vector<int> e[N]; void dfs(int x, int col) { c[x] = col; for (auto y : e[x]) if (!c[y]) dfs(y, 3 - col); } int main() { n = read(); for (int i = 1; i <= n; i ++) { x[i] = read(), y[i] = read(); e[x[i]].pb(y[i]), e[y[i]].pb(x[i]); } for (int i = 1; i <= n; i ++) e[i * 2 - 1].pb(i * 2), e[i * 2].pb(i * 2 - 1); for (int i = 1; i <= n * 2; i ++) if (!c[i]) dfs(i, 1); for (int i = 1; i <= n; i ++) printf("%d %d\n", c[x[i]], c[y[i]]); return 0; }
- 1
