题解：P12204 [COI 2022] 委员选举 / Povierenstvo

· · 题解

首先猜测保证没有奇环就绝对有解。输出 -1 即可验证。首先考虑入度为 0 的点，我们考虑选择它并删除它的后继，进入子问题继续构造，发现最后可能会剩下若干个强连通分量。

考虑从入度为 0 的强连通分量入手，此时一个强连通分量中有一个性质，就是它是一个二分图，不难发现可以直接染色就是对的，然后对于染黑的点把其后继删除，然后我们继续处理这个子图，然而这样是 \mathcal{O}(nm) 的。

我们发现我们没必要删除之后重新跑一遍删入度为 0 的点和 tarjan，我们考虑还是对于当前入度为 0 的强连通分量处理，他是一张二分图，但是我们得钦定入度为 0 的点必选，强制选了之后发现这个原图上的强连通分量又变成了若干个点数大于 1 的强连通分量，此时我们黑白染色绝对没问题。

所以这道题我们直接缩点，然后在缩完后的 DAG 上跑拓扑排序，对于每个强连通分量先处理入度为 0 的点再染色，最后把黑点后继删除就行了。