Codeforces 840B

发表于 |

题目

给$N$个点$M$条边的连通图，每个点$i$上有权值$d[i]\in{-1,0,1}$。要你选出一些边保留，其余边删去，使得每个$d\neq-1$点的度数模$2$等于$d[i]$，权值为$-1$的点没有要求。

数据范围

$1\leq N \leq 3\times 10^5 \quad N-1\leq M\leq 3\times10^5$

做法

构造性证明如下结论：本题有解当且仅当能通过将权值为$-1$的点的权值变为$0$或者$1$，使得所有点的权值和为偶数。

充分性：证逆否命题。若度数和只能是奇数，则显然无解。因为最后答案中的每个连通块的度数都是偶数，和必然是偶数。

必要性：构造性证明。随便生成一个生成树，任取一点为根。对每个节点，按照深度从下向上处理。设当前节点为$cur$，其父亲节点为$fa$。

  1. 若$cur$的权值为$0$，则$cur$不需要处理，丢弃$cur$，此时剩余点度数和仍为偶数。
  2. 若$cur$的权值为$1$，则选取边$(cur, fa)$，并将$fa$的权值取反，丢弃$cur$，此时剩余点的度数和仍为偶数。

这样处理完所有点，即可得到答案。

代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 5;
struct Edge {int to, id;};
struct Node
{
  int dep, id;
  Node () {}
  Node (int dep_, int id_) : dep(dep_), id(id_) {}
  bool operator < (const Node &b) const
  {
    return dep < b.dep;
  }
};
int N, M;
int d[MAX_N];
vector<Edge> G[MAX_N];
int fa[MAX_N];
int en[MAX_N];
bool vis[MAX_N];
priority_queue<Node> que;
vector<int> ans;
bool inque[MAX_N];
int dep[MAX_N];
void addEdge(int a, int b, int id)
{
  G[a].push_back((Edge){b, id});
  G[b].push_back((Edge){a, id});
}
void dfs(int v)
{
  bool isLeaf = true;
  for (int i = 0; i < G[v].size(); ++i) {
    Edge &e = G[v][i];
    if (!vis[e.to]) {
      vis[e.to] = true;
      fa[e.to] = v;
      dep[e.to] = dep[v] + 1;
      en[e.to] = e.id;
      dfs(e.to);
      isLeaf = false;
    }
  }
  if(isLeaf) {
    que.push(Node(dep[v], v));
    inque[v] = true;
  }
}
void dfs2(int v, int p, int eid)
{
  for (auto e : G[v]) {
    if (!vis[e.to]) {
      vis[e.to] = true;
      dfs2(e.to, v, e.id);
    }
  }
  if (d[v] == 1) {
    ans.push_back(eid);
    d[p] ^= 1;
  }
}
void solve()
{
  while (!que.empty()) {
    Node v = que.top(); que.pop();
    inque[v.id] = false;
    if (d[v.id] == 1) {
      d[fa[v.id]] ^= 1;
      if(!inque[fa[v.id]]) {
        que.push(Node(dep[fa[v.id]], fa[v.id]));
        inque[fa[v.id]] = true;
      }
      ans.push_back(en[v.id]);
    } else if (fa[v.id] != -1) {
      if(!inque[fa[v.id]]) {
        que.push(Node(dep[fa[v.id]], fa[v.id]));
        inque[fa[v.id]] = true;
      }
    }
  }
  printf("%u\n", ans.size());
  for (int i = 0; i < ans.size(); ++i) {
    printf("%d\n", ans[i]);
  }
}
int main()
{
  cin >> N >> M;
  int sumD = 0, numn1 = 0, idxn1;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &d[i]);
    if (d[i] != -1) sumD += d[i];
    else numn1++, idxn1 = i;
  }
  for (int i = 0; i < M; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    --a; --b;
    addEdge(a, b, i + 1);
  }
  if (numn1 == 0 && sumD % 2 == 1) {
    printf("-1\n");
    return 0;
  }
  if (sumD % 2 == 1) {
    d[idxn1] = 1;
  }
  for (int i = 0; i < N; ++i) {
    if (d[i] == -1) d[i] = 0;
  }
  fa[0] = -1;
  vis[0] = true;
  dfs(0);
  //dfs2(0, -1, -1);
  solve();
  return 0;
}