codeforces 454 E. Little Pony and Summer Sun Celebration（构造+思维）

题目链接：http://codeforces.com/contest/454/problem/E

题意：给出n个点和m条边，要求每一个点要走指定的奇数次或者是偶数次。

构造出一种走法。

题解：可能一开始会难以入手。其实要想改变这个点的奇偶次数只要回去上一个节点再回来就行。然后上一个节点会在

dfs回朔时再进行修改最后只要关注起点就行了。

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
const int M = 1e5 + 10;
vector<int>vc[M] , path;
int num[M];
bool vis[M];
void dfs(int u , int pre) {
    int len = vc[u].size();
    path.push_back(u);
    num[u] ^= 1;
    vis[u] = true;
    for(int i = 0 ; i < len ; i++) {
        int v = vc[u][i];
        if(!vis[v] && v != pre) {
            dfs(v , u);
            path.push_back(u);
            num[u] ^= 1;
        }
    }
    if(num[u] == 1 && pre != -1) {
        num[u] ^= 1;
        num[pre] ^= 1;
        path.push_back(pre);
        path.push_back(u);
    }
}
int main() {
    int n , m;
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i < m ; i++) {
        int u , v;
        scanf("%d%d" , &u , &v);
        vc[u].push_back(v);
        vc[v].push_back(u);
    }
    for(int i = 1 ; i <= n ; i++) {
        scanf("%d" , &num[i]);
    }
    int pos = 1;
    for(int i = 1 ; i <= n ; i++) {
        if(num[i] == 1) {pos = i; break;}
    }
    memset(vis , false , sizeof(vis));
    dfs(pos , -1);
    if(num[pos] == 1) path.resize(path.size() - 1);
    int flag = 0;
    for(int i = 1 ; i <= n ; i++) {
        if(!vis[i] && num[i] == 1) {flag = 1; break;}
    }
    if(flag) printf("-1
");
    else {
        printf("%d
" , path.size());
        for(int i = 0 ; i < path.size() ; i++) {
            printf("%d " , path[i]);
        }
        printf("
");
    }
    return 0;
}