AT_agc074_a [AGC074A] Communicate Topological Order 笔记

CLIST *2000 做不出来，活该退役。

由于边有明确的从小到大指向的关系，并且这是拓扑图，所以考虑按 $P_i$ 从小到大做。设 $f_i$ 表示当青木知道了 $P\in [1,i]$，最多有多少个点可以不告诉青木，那么有两种情况。

• 直接告诉青木，$f_i\leftarrow f_{i-1}$。
• 青木猜出 $P_u$ 是什么，那么显然有
  • 青木知道 $max{P}_{\mathrm{fa}(u)}$，不然他无法确定 $P_u$ 的下界。
  • 青木知道 $(max{P}_{\mathrm{fa}(u)},P_u)\ne P_u$，否则他无法确定 $P_u$，因此只有把 $(,)$ 全部告诉青木，才能不告诉他 $P_u$。
• 即 $f_i\leftarrow f_{max{P}_{\mathrm{fa}(u)}}+1$。

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