Description

给一个无向图，$n$​​​ 个点 $m$​​ 条边，给定一个 01 序列，如果 $a_i=1$​，要求走到这个点奇数次，否则，要求走到这个点偶数次，请你任选起点，输出满足要求的经过点的序列和序列长度，序列长度不能超过 $4n$。

Solution

没思路的时候看到 CF 标签上的 “DFS”，于是考虑乱搞，然后就搞出来了。

首先任选一个要求走奇数遍的一个点进行 DFS。我们先不考虑图的形状，找一棵 DFS 树出来，然后遍历，如果回溯的时候发现这个点的奇偶性不对，我们走到它的父亲，再走回来，这样奇偶性就对了。然后一算：遍历 $2n$，处理一个奇偶性错误需要走 $2$ 个点，上界 $4n$​，于是这道题就做完了。

注意到不一定是个联通图，那么考虑如果一个联通块内全是偶数，我们直接不走即可；如果存在奇数，那么必须走。

那么当有超过一个联通快内有奇数时，无解。

小问题：如果选择的根奇偶性不对，我们先正常改，然后把答案减掉 $3$ 即可（即不走回到根节点）。

Code

存答案的时候建议用 vector 而不是数组，我一开始忘记了 $4n$ 这回事导致 RE。

#include <cstdio>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;

int a[maxn], ans[maxn * 4], father[maxn], vis[maxn], m, n, now[maxn];
int cnt = 0;

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y), e[y].push_back(x); }

void dfs(int x, int fa)
{
    vis[x] = 1, father[x] = fa;
    ans[++cnt] = x, now[x] ^= 1;
    for (int v : e[x])
    {
        if (vis[v])
            continue;
        dfs(v, x);
        ans[++cnt] = x, now[x] ^= 1;
    }
    if (now[x] != a[x])
    {
        ans[++cnt] = fa;
        ans[++cnt] = x;
        now[x] ^= 1, now[fa] ^= 1;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0, x, y; i < m; i++)
        cin >> x >> y, add(x, y);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        if (a[i] == 1)
        {
            dfs(i, 0);
            break;
        }

    for (int i = 1; i <= n; i++)
        if (!vis[i] && a[i])
        {
            cout << -1 << endl;
            return 0;
        }

    if (ans[cnt - 1] == 0 && cnt >= 3)
        cnt -= 3;
    cout << cnt << endl;
    for (int i = 1; i <= cnt; i++)
        cout << ans[i] << (i == cnt ? "\n" : " ");
}