Leha and another game about graph CodeForces – 840B (dfs)

链接

大意: 给定无向连通图, 每个点有权值$d_i$($-1\leq d_i \leq 1$), 求选择一个边的集合, 使得删除边集外的所有边后, $d_i$不为-1的点的度数模2等于权值

首先要注意到该题只需要考虑dfs树即可, 因为反向边一定不会产生贡献

存在权值为-1的点, 则直接以权值为-1的点为根dfs

若无权值为-1的点, 则答案不一定存在, 任选一个点为根dfs即可

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <vector>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;const int N = 4e5+10, INF = 0x3f3f3f3f;
int a[N], b[N], c[N], vis[N], f[N], n, m, k, t;
vector<pii> g[N];void dfs(int x) {
if (vis[x]) return;
vis[x]=1;
for (auto e:g[x]) {
dfs(e.x);
if (a[e.x]==1) a[e.x]=0,f[e.y]^=1,a[x]^=1;
}
}int main() {
scanf("%d%d", &n, &m);
int rt = 1;
REP(i,1,n) scanf("%d", a+i),a[i]==-1?rt=i:0;
REP(i,1,m) {
int u, v;
scanf("%d%d",&u,&v);
g[u].pb({v,i}),g[v].pb({u,i});
}
dfs(rt);
if (a[rt]==1) return puts("-1"),0;
int cnt = 0;
REP(i,1,m) cnt += f[i];
printf("%d\n", cnt);
REP(i,1,m) if (f[i]) printf("%d ",i);
puts("");
}