题解 CF527E 【Data Center Drama】
xht
2020-02-12 15:54:59
> [CF527E Data Center Drama](https://codeforces.com/contest/527/problem/E)
## 题意
- 给定一张 $n$ 个点 $m$ 条边无向图。
- 你需要加尽可能少的边，然后给所有边定向，使得每一个点的出入度都是偶数。
- 边可以是自环，也可以由重边。
- $n \le 10^5$，$m \le 2 \times 10^5$。
## 题解
若每个点的出入度都是偶数，则每个点的总度数是偶数，而这是一张图存在**欧拉回路**的充要条件。
所以将所有总度数为奇数的点两两相连。
但是并不是所有存在欧拉回路的图都满足条件，还需要满足边数为偶数。
那么随便找一个点加一个自环即可。
这显然是最少的加边方案。
最后跑一个欧拉回路出来，然后隔一条边换一个方向即可。
## 代码
```cpp
const int N = 1e5 + 7, M = 1e6 + 7;
int n, m, h[N], e[M], t[M], tot = 1, d[N], v[M], k;
vi p;
inline void add(int x, int y, int o = 1) {
e[++tot] = y, t[tot] = h[x], h[x] = tot;
if (o) ++d[x], ++d[y], add(y, x, 0);
}
void dfs(int x) {
for (int &i = h[x]; i; i = t[i]) {
if (v[i]) continue;
v[i] = v[i^1] = 1;
int y = e[i];
dfs(y);
if ((++k) & 1) print(x, ' '), print(y);
else print(y, ' '), print(x);
}
}
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), add(x, y);
for (int i = 1; i <= n; i++) if (d[i] & 1) p.pb(i);
for (ui i = 0; i < p.size(); i += 2) add(p[i], p[i+1]), ++m;
if (m & 1) add(1, 1), ++m;
print(m), dfs(1);
return 0;
}
```