D - Leha and another game about graph
思路：首先，如果所有点的度数加起来是奇数，且没有-1，那么是不可以的。
其他情况都可以构造，我们先dfs出一个生成树，然后从叶子节点开始往上处理
对于节点u和v，边u -> v，如果d[v]等于1，那么就要选这条边，d[u]取反（改变状态）
这样的话v就可以不用管了，一直这样下去直到根节点，出了根节点，其他点都能满足
如果存在-1，就把-1放在根节点，如果没有的话，以任意节点为根都可以，因为奇偶性
不变。
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 3e5 + 10; int d[N]; vector<pii> g[N]; vector<int> ans; bool vis[N]; void dfs(int u) { vis[u] = true; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i].fi; if(!vis[v]) { dfs(v); if(d[v] == 1) { ans.pb(g[u][i].se); if(d[u] != -1) d[u] ^= 1; } } } } int main() { int n, m, u, v, sum = 0, rt = 1; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &d[i]); for (int i = 1; i <= n; i++) { if(d[i] != -1) sum += d[i]; else { rt = i; sum = 0; break; } } for (int i = 1; i <= m; i++) { scanf("%d %d", &u, &v); g[u].pb({v, i}); g[v].pb({u, i}); } if(sum&1) puts("-1"); else { dfs(rt); printf("%d ", (int)ans.size()); for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]); } return 0; }