P17223 [ICPC 2017 Nanning R] The Maximum Unreachable Node Set 题解

思路

朴素的想法是对于任意能到达 $v$ 的 $u$，连无向边 $(u,v)$ 然后求图的最大独立集，然而这是困难的。

前置知识：在偏序集中，一个链是指集合中的元素可以相互比较大小的子集，而一个反链则是指集合中任意元素之间都不可比较大小的子集。在这里如果把有向边视作偏序关系，那么根据定义，求最大不可达节点集就是在求最长反链的长度。

Dilworth 定理告诉我们，最长反链等于最小链划分中链的个数，这也是在图上选出若干条路径后，满足所有路径 $P$ 作为集合的并为 $V=\{1,2,3,\cdots,n\}$ 的最小路径条数。对于前后两句话这里都不作证明。

最小链划分怎么求？

对于每一个点，其在最小链划分的入度和出度都不大于 $1$。把每个点拆成入点和出点。对于原图上每一对可达的 $(u,v)$，连无向边 $(u_{\textbf{out}},v_{\textbf{in}})$。

对新图跑二分图最大匹配。开始时，整个图被划分成 $n$ 条链，每个链是一个孤点。往匹配里添加 $(u_{\textbf{out}},v_{\textbf{in}})$ 这条边相当于，将以 $v$ 为链头的链接在了以 $u$ 为链尾的链之后。注意这里的链跟图论的链是不同的概念，$u,v$ 之间不一定要直接有边，只要 $u$ 能到达 $v$ 即可。

新图上的匹配与原图上的链覆盖存在双射关系。

初始时有 $n$ 条链，匹配里每增加一条边链的数量就减少 $1$，因此答案是 $n-k$，$k$ 是最大匹配的边数。

时间复杂度 $\mathcal{O}(n^3)$。