Codeforces 841D(DFS)

Codeforces 841D
题意：给出一个连通图，每个点有一个权值$d_i$, 只有$0,1,-1$三种值。先在在原图中求出一个子边集使得所有点满足$d_i=-1$或者$i$点的度数模$2=d_i$, 输出任何一个方案。

考虑一条边一条边地加。
首先如果不选一条边，那么$di=-1$或者$di=0$的点能满足题意，因为度数都为0。而$d_i=1$的不满足。所以我们从任何一个点开始DFS(连通图可以选择任意节点)，如果某个点有一个儿子$d=1$，那么这条边必须要反选(之前选就不选，之前不选就选)，然后把儿子的$d$置为0，这个点的$d$取反。(因为多了一条边或者少了一条边，度数奇偶性变化)。最后就是如果节点1的$d=1$，那么没有父亲给他反选，怎么办？我们找到一个$d=-1$的点，然后把这个点到节点1的路径全部反选。这样只有节点1和这个点的奇偶性发生变化，而$d=-1$无视奇偶问题，所以这样就完美解决了。
如果节点1的$d=1$，又没有$d=-1$的点，那么无解

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
#define mp make_pair
#define pll pair<LL, LL>
vector<pll> G[300000 + 5];
int n, m, di[300000 + 5], vis[300000 + 5], sel[300000 + 5];
pll fa[300000 + 5];
void ins(int x, int y, int ith) {
    G[x].push_back(mp(y, ith)), G[y].push_back(mp(x, ith));
}
void dfs(int u, int pa) {
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i].first, bh = G[u][i].second;
        if (v == pa || vis[v]) continue;
        vis[v] = true, fa[v] = mp(u, bh);
        dfs(v, u);
        if (di[v] == 1) {
            sel[bh] ^= 1;
            di[v] = 0;
            di[u] ^= 1;
        }
    }
}
void clean() {
    for (int i = 1; i <= n; i++) vis[i] = fa[i].first = fa[i].second = 0;
    for (int i = 1; i <= m; i++) sel[i] = 0;
}
void solve() {
    clean();
    int nd = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &di[i]);
        if (di[i] == -1) nd = i;
    }
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        ins(u, v, i);
    }
    vis[1] = true, dfs(1, -1);
    if (di[1] == 1) {
        if (nd == 0) {printf("-1\n"); return ;}
        while (nd != 1) {
            sel[fa[nd].second] ^= 1;
            nd = fa[nd].first;
        }
    }
    int taki = 0;
    for (int i = 1; i <= m; i++) if (sel[i]) taki++;
    printf("%d\n", taki);
    for (int i = 1; i <= m; i++) if (sel[i]) printf("%d ", i);
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}