题意
有一个由 \(n\) 个点 \(m\) 条边组成的无向图，边有边权 \(w\in\{1,2\}\)，现要求给这 \(n\) 条边定向，使得对于每个点 \(u\) 有：连向 \(u\) 的边的权值和与 \(u\) 连出的边的权值和之差的绝对值为 \(1\)。
思路
首先可以发现，连进 \(u\) 一条边再连出 \(u\) 一条权值相同的边，是可以把权值抵消的，考虑对于每个 \(u\)，我们都尽量去抵消这些边，所以，最终剩下来的边有四种情况：
-
没有边，明显不合法；
-
只有一条边权为 \(2\) 的边，也不合法；
-
只有一条边权为 \(1\) 的边，方向无所谓；
-
有一条边权为 \(1\) 的边，还有一条边权为 \(2\) 的边，方向相反就合法。
所以情况 3 也等价于度数（不是边权和）为奇数，情况 4 等价于度数为偶数。
先考虑如何去抵消这些边，发现一条边连进来之后又要出去，最终会连成一个闭环，这不就是欧拉回路吗，于是，我们可以进行两次找欧拉回路，一次只走边权为 \(1\) 的边，另一次走边权为 \(2\) 的。
接下来考虑给剩下来的边定向，观察情况 4，这不也是一条边连进一条边连出吗，继续欧拉回路，又因为保证合法，所以只剩下情况 3 了，我们尝试给它“补一条边”，让这个点也能连进然后连出走回路，于是想到建一个新点，把所有这种点连向新点，边的权值为 \(1\)，此时就相当于和剩的那条边抵消，发现因为本图是无向图，所以度数和为偶数，所以情况 3 的点的个数也为偶数，于是新点也连了偶数条边，至此，全图的点都连了偶数条边，可以直接跑欧拉回路。
发现这样实现有点复杂，我们考虑只用一次欧拉回路求出答案，假设到达该点的边权值为 \(w_{lst}\)，那么我们优先走权值等于 \(w_{lst}\) 的边，也就是优先抵消边，如果没有，说明当前权值的边只有 \(1\) 条了，那么连向其他的任意一条边就行了，最后在建边时把边权不同的边分开建，找回路加上当前弧优化（不访问访问过的点）时标记每条边的方向输出就行了。
时间复杂度 \(O(n+m)\)，空间复杂度 \(O(m)\)。
标签：一条,边权,偶数,P7816,权值,条边,欧拉 From： https://www.cnblogs.com/BINYU/p/17962543