P1653 题解

Linge_Zzzz · 2024-07-04 17:22:50 · 题解

不难想到根据高度之间的偏序关系进行缩点。

下面证明答案为 入度为零的点 和 出度为零的点 的最大值。

设 S 为入度为零的点列，T 为出度为零的点列。

要证答案为 \max\{|S|,|T|\}。

首先给出一种构造方案。

不妨假设 |S|\leq|T|，这样可免去讨论而不失一般性。

现先对 |S|=|T| 的情况构造，然后说明 |S|<|T| 的情况可以化归到 |S|=|T| 的情况。

我们构造 S_i \to T_{i+1}(i=1,2,3,\cdots,|T|-1) 和 T_{|T|}\to S_1。这张图上每个点都至少被包含在一个一个环里，故是一个合法的构造。

对于 |S|<|T| 的情况，我们构造 T_i\to T_{i+1}(i=1,2,3,\cdots,|T|-|S|)。现在即转化到上述情况。

下面证明答案大于等于 \max\{|S|,|T|\}。

显然的结论，若一个图是强连通的，则其一定没有入度为零的点和出度为零的点。

（这个结论的逆命题不成立，也是许多题解里的错误）

所以，对于每一个入度/出度为零的点，我们都要将其向内/向外连边。

若两两配对，可达到可能的最少数量，所以答案大于 \max\{|S|,|T|\}。

综上所述，答案为 \max\{|S|,|T|\}。