通过欧拉回路及其相关性质对边进行定向：CF527E

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135107666

https://www.luogu.com.cn/problem/CF527E

出入度都为偶数？而且还联通 ?明摆和欧拉图、欧拉路径相关。

可以先猜一个结论，当所有点度数都为偶时，一定可以成功定向。

先看无向图。首先一个点的度数，必须为偶数。而无向图一条边的贡献为2，所以恰有偶数个奇点，两两匹配后完成。一条边的贡献是一入度一出度，而入度和出度的和分别肯定都是偶数，所以至少要有偶数条边，我们可以直接来个自环。

此时可以上欧拉科技了。考虑欧拉路径，长度必然为偶数，同时必然为偶数。如果我们相邻之间的取反，恰好能对应2出2入。