[AGC077C] Reverse and DAG

PTqwq · 2026-07-26 13:39:33 · 题解

首先显然可以将边的方向看成边是否存在。

根据星图的结论：

• 定义操作为选一个大小恰好为 k 的点集，将其导出子图内的边的存在性都反转。
• 则图 G 能操作成图 H 当且仅当：
  • 若 k \bmod 2 = 1：对于任意的节点 u，有 u 在 G 中的度数与 u 在 H 中的度数奇偶性相同。
  • 若 k \bmod 4 = 0,1：G 与 H 的边数奇偶性相同。

但是本题并不是对完全图操作，考虑转化，将原图 G 任意加边补成一张竞赛图 G'，如果存在一个 G' 有解则 G 也一定有解，反之如果 G 有解，则也可以根据拓扑序构造对应的 G'，所以转化是等价的。

我们暂时不管如何补全成 G'，先考虑对于一个 G' 如何简化条件：此时第二个限制转化成方向不变的边数是偶数，第一个限制转化为所有点入度奇偶性不变。

考虑最终得到的 DAG 竞赛图的拓扑序：[p_1, p_2, \dots, p_n]，这里边数可以看成是 p 的逆序对数（我们只关心奇偶性！），而入度的奇偶性可以看成是下标的奇偶性反转。如果逆序对奇偶性不对，我们可以交换 p_1, p_3 在不改变所有点入度奇偶性的情况下改变逆序对数的奇偶性，所以第二个条件可以不考虑。

此时如果 k \bmod 2 = 0 则一定有解，否则要求 G' 中入度是奇数的点的数量恰好为 \left\lfloor\dfrac{n}{2}\right\rfloor。

考虑 G 看成无向图后的补图 H，那么我们需要给 H 定向然后把入度加给每个点，可以发现对于每个 H 的连通块，只需要限制入度之和的奇偶性等于边的奇偶性即可，证明可以考虑取出 DFS 树可以做到满足除了根以外所有点的要求。

这样如果我们知道了 H 的连通块信息，那么入度为奇数的点的数量的范围可以轻松求出，而求 H 的连通性可以 DFS，每次用 std::set 求出一个邻居即可。

时间复杂度 O((n+m) \log n)。

https://atcoder.jp/contests/agc077/submissions/77876030