problem

一张简单无向图, 给出每个点的奇偶性.

找到一条路径(边可经过多次)使得路径上点出现的奇偶性与要求相同.

要求路径长度不超过 4n

  • n\leq 10^5

sol

图不一定连通.

所以那些出现次数为奇数的点一定在一个连通块.

考虑图转树, 对这个连通块建立生成树.

从根开始\text{dfs} 这棵树, 每次到一个点(u)就将其加入答案.

如果\text{dfs}u的子树vv的奇偶性不对, 就再走一次(u,v).

最终若根节点奇偶性不对, 那么开始就不从根\text{dfs}, 即删去它最开始的一次.

Code

#include 
using namespace std;

const int N = 1e5 + 50;
# define pb push_back

int n, m, u, v, cnt, root, a[N], vis[N];
int Ecnt, first[N], nex[N], arr[N];
vector g[N], ans;

inline int add(int u, int v) {
  nex[++Ecnt] = first[u], first[u] = Ecnt, arr[Ecnt] = v;
}
void dfs(int u) {
  cnt -= a[u];
  vis[u] = 1;
  for(int i = 0, v; i < (int) g[u].size(); ++i) {
    v = g[u][i];
    if(vis[v]) continue;
    add(u, v);
    dfs(v);
  }
}
void Dfs(int u, int fa = 0) {
  ans.pb(u), a[u] ^= 1;
  for(int i = first[u], v; i; i = nex[i]) {
    v = arr[i];
    if(v == fa) continue;
    Dfs(v, u);
    ans.pb(u), a[u] ^= 1;
    if(a[v]) {
      ans.pb(v), a[v] ^= 1;
      ans.pb(u), a[u] ^= 1;
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    scanf("%d%d", &u, &v);
    g[u].pb(v), g[v].pb(u);
  }
  for(int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    cnt += a[i];
    if(a[i] & 1) root = i;
  }
  dfs(root);
  if(cnt) return 0 * printf("-1\n");
  Dfs(root);
  if(a[root]) {
    reverse(ans.begin(), ans.end());
    ans.pop_back();
    reverse(ans.begin(), ans.end());
  }
  printf("%d\n", ans.size());
  for(int i = 0; i < (int) ans.size(); ++i)
    printf("%d ", ans[i]);
  return 0;
}