CF527E Data Center Drama 题解

CF527E Data Center Drama

题意

• 给定一张 $n$ 个点 $m$ 条边无向图。
• 你需要加尽可能少的边，然后给所有边定向，使得每一个点的出入度都是偶数。
• 边可以是自环，也可以由重边。
• $n \le 10^5$，$m \le 2 \times 10^5$。

题解

若每个点的出入度都是偶数，则每个点的总度数是偶数，而这是一张图存在欧拉回路的充要条件。

所以将所有总度数为奇数的点两两相连。

但是并不是所有存在欧拉回路的图都满足条件，还需要满足边数为偶数。

那么随便找一个点加一个自环即可。

这显然是最少的加边方案。

最后跑一个欧拉回路出来，然后隔一条边换一个方向即可。

代码

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;
}