CF1977E

sunkuangzheng · 2024-05-27 00:38:32 · 题解

笑点解析：

显然图的形态只有两种可能：

• 弱连通。
• 两条不连通的链，可能有额外边。

第二种情况由于图是 dag 非常好做。

考虑第一种情况，我们对图拓扑排序后一层最多有 2 个点，那么原图可以用两条链覆盖，现在我们需要找到它们。

我们首先找到两条链的链头，钦定第一条链链头是 1，容易找到第一个分叉，可以找到第二条链头 y，此时第一条链尾是 x = y - 1。

考虑依次加入 x+1,\ldots,n，有一个很 naive 的思路是对于点 i 如果 x 能到 i 就加入第一条链，否则第二条。但是会被以下图卡掉：1 \to 3,2 \to 3,1 \to 4。此时如果你将点 3 划给链 1 则 2 号点和 4 号点不可达。因此，我们需要额外维护公共可达链，记为 3 号链，链尾为 z。（请注意，3 号链是一条链，也不能存在分叉）

然后我们又有一个 naive 的思路：如果点 i 从 x,y 都可达，就加入链 3，否则加入到不了的点。但是考虑图 1 \to 3,2 \to 3,3 \to 4,4 \to 5,4 \to 6，按照这个算法得到的链 3 并不是链。

问题在于我们想要知道点 i 对于 x,y,z 三个点的可达性，但我们只有 2n 次询问机会。分讨一些情况，发现有一次询问是可以省略的：

• 如果链 3 为空，则：
  • 如果 x,y 只有一个点可以到 i，则直接划入对应的链。
  • 否则，加入链 3。
• 否则，
  • 如果 z 可以到达 i，加入链 3。
  • 否则，
    • 如果 x 可以到达 i，将链 3 全部划入链 2，并将 i 划入链 1。
    • 否则，将链 3 全部划入链 1，并将 i 划入链 2。

容易发现以上做法的询问次数不超过 2n，且正确性较为显然。

赛时 AC 记录。