CodeForces - 453C Little Pony and Summer Sun Celebration

博主的 BiBi 时间

小马宝莉。。。在博主的少年时代是博主即使不做作业也要看的动画片。

然而，还是没有读对题。

Description

• 图可能有几个连通块。
• 不能从每个连通块重新开始。

Solution

其实思路很新奇。

把图化成树。如果儿子的奇偶性不对，就走到父亲再回来。父亲同理。

对于根节点没有爸爸，可以通过最后是否停在根节点来改变奇偶性。

关于根节点的选取，我们尽量选择 $a$ 值为 $1$ 的。因为可能只有一个 $1$，但是不与外界相连的情况。

Code

#include <cstdio>
#include <vector>
using namespace std;const int N = 1e5 + 5;int n, m, a[N], s[N];
bool vis[N];
vector <int> e[N], ans;int read() {int x = 0, f = 1; char s;while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();return x * f;
}void dfs(const int u, const int root, const int fa) {ans.push_back(u); s[u] = 1; vis[u] = 1;for(int i = 0; i < e[u].size(); ++ i) {int v = e[u][i];if(vis[v]) continue;dfs(v, root, u);}if(u == root && s[u] != a[u]) {ans.pop_back(); s[u] ^= 1;return;}if(u == root) return;if(s[u] != a[u]) {ans.push_back(fa); ans.push_back(u);s[u] ^= 1; s[fa] ^= 1;} ans.push_back(fa); s[fa] ^= 1;
}bool ok() {for(int i = 1; i <= n; ++ i) if(s[i] != a[i]) return 0;return 1;
}int main() {int u, v;n = read(), m = read();for(int i = 1; i <= m; ++ i) {u = read(), v = read();e[u].push_back(v); e[v].push_back(u);}for(int i = 1; i <= n; ++ i) a[i] = read();int start = 1;for(int i = 1; i <= n; ++ i)if(a[i] == 1) start = i;dfs(start, start, 0);if(! ok()) return puts("-1"), 0;printf("%d\n", ans.size());for(int i = 0; i < ans.size(); ++ i) printf("%d ", ans[i]);return 0;
}