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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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;
}

------ 本文结束 ------