CF1994F Stardew Valley（欧拉回路）

题意简述

给定 \(n\) 个点 \(m\) 条边，每条边分为关键边和非关键边，你需要构造一条回路，使得每条边被至多经过一次，而关键边恰好被经过了一次，无解输出 -1。保证所有关键边将原图连通。

\(n,m\le5\times10^5\)。

分析

先做一个比较关键的题意转化：求是否可以将图上的一些非关键边删掉，使得原图存在欧拉回路。

而欧拉回路存在的充要条件是图连通且所有点的度数为偶数，由于图保证连通所以只需考虑后一个条件。设 \(deg_i\) 表示 \(i\) 点度数的奇偶性。“加入一条边”就相当于反转边的端点的奇偶性。由于关键边必然存在，所以先强制把关键边加入，问题转化为现在每个点有一个 \(deg_i\) 的权值，可以选择一些边加入，使得所有点的 \(deg_i=0\)。

而这是一个经典问题：对所有非关键边求出一颗 DFS 树森林，考虑从下往上转移，对于一条树边 \((u,v),dep_u<dep_v\)，若 \(deg_v=1\)，则选出这条边；否则不选。若森林的每棵树的根节点的 \(deg\) 都是 \(0\) 就合法，否则不合法。在此不做证明。还有一个小扩展：若有解，无论非树边选还是不选，都存在一个给树边定缺的方案使得解合法（只需要把非树边两端在树上的路径上的边状态取反即可）。

求出来了要加入的非关键边之后只需要建新图跑欧拉回路即可。线性。