AtCoder-abc345_f题解

题意简述

给定一个无向图。你要在其中选出一些边，使得选出的边所构成的图中，度数为奇数的点有 \(K\) 个。如果可以，输出选了哪些边，否则输出 -1。

思路

首先在选一条边时，边两端点度数的奇偶性一定都会改变，即要么都变为奇数，要么两个点的奇偶性交换过来，要么都变为偶数。这三种情况时满足条件的点的个数分别变为 \(+2,0,-2\)。因此无论怎么选边，度数为奇数的点只能有偶数个。所以 \(K \equiv 1 \pmod 2\) 时一定无解。

题目没说图一定连通，所以我们可以对每个连通块分别处理。所以我们只需要处理单个连通块。

假设这个连通块有 \(N\) 个节点，那么这个连通块在选边后最多能有几个点的度数为奇数呢？

答案是 \(N-(N \bmod 2)\)，即不大于 \(N\) 的最大偶数。为什么呢？

我们先求出这个图的 DFS 树。此时树中有 \(N-1\) 条边。在 DFS 时，同时维护子树大小 \(sz\) 和搜索时该点度数的奇偶性 \(li\)（奇数为 \(true\)，偶数为 \(false\)）。

我们在遍历的时候，假设遍历到了 \(u \to v\) 这条边，\(u\) 的父亲是 \(f\)。如果 \(li_v=false\)，就选择 \(u \to v\) 这条边，并把 \(li_v\) 标记为 \(true\)，\(li_u\) 反转。便利完所有出边后，会有下面几种情况：

• \(li_u=true\)

此时 \(u\) 已经满足条件了。回到 \(f\) 时，\(f \to u\) 的这条边不会被选。对 \(u\) 的搜索结束，\(u\) 可以满足条件。

• \(li_u=false\)

此时 \(u\) 没有满足条件。那么在回到 \(f\) 时，则会选择 \(f \to u\) 这条边，使得 \(u\) 满足条件。

这么看来所有的点都会满足条件，除了根节点。如果 \(N \equiv 1 \pmod 2\)，则除根节点之外的点都已经满足条件，根节点无法满足条件。否则根节点也可以满足条件。

我们在搜索的时候可以记录还需要让多少个点满足条件。设这个值为 \(w\)。那么我们在选边的时候，根据上面遍历到 \(u \to v\) 时的几种情况再做出相应做法：

• \(w=0\)

这条边不选即可。

• \(w>0\)

• • \(li_v=false\)

我们选择这条边，使得 \(v\) 满足了条件，\(w \gets w-1\)。

接下来我们计算出 \(li_u\)，如果为 \(true\)，则该点由不满足条件变为满足条件，\(w \gets w-1\)。否则该点由满足条件变为不满足条件，\(w \gets w+1\)。

• • \(li_v=true\)

这条边不选即可。

可以发现，在选择一条边后，\(w\) 值要么不变，要么 \(-2\)。这样最后如果 \(w=0\)，则有解，否则无解。

到这里，最后一个问题就是记录选择哪些边了。我们可以使用链式前向星存图，因为是无向图，每个边存两次。我们可以从编号 \(2\) 开始存，第一条边的编号为 \(2,3\)，第二条为 \(4,5\)。我们再用一个 \(ans\) 数组，如果这条边选了，我们把对应边编号的 \(ans\) 值设为 \(true\)。这样每条边编号除以二下取整就是它实际边的编号。

那么这个问题就解决了。

代码