先回顾一下题目吧，给定一个$n$个元素的偏序集(就当是DAG的传递闭包)，求：

1)最长反链的长度；

2)一个最长反链；

3)哪些元素可能在最长反链中。

很久以前看到这个题的时候我还没有意识到它就是dilworth定理。。。然后看着题解做了第一问。觉得“第二问好像很水的样子，随便构造就出来了”，可是试了很多种方案都没有构造出来。百度上搜到的blog都是“bzoj上只有第一问的数据，那么我就只做第一问吧”，然后问了一些同学他们也不知道第二问怎么做的样子。某天膜了一下vfk的博客，发现了dilworth定理的一个证明，可惜不是构造性的(就是我不能看着这个证明就构造处一个最长反链)。

最近几天搜到了一个网页。

我就抄袭一下这个上面的内容，顺便orz回答这个问题的大爷。。。

回忆一下最小链覆盖的求法。令$n$为偏序集的点数，建立一个二分图，$X$部的$i$号点用$x(i)$表示，$Y$部的$i$号点用$y(i)$表示。对于偏序集中的一条关系$u < v$，在$x(u)$与$y(v)$之间连边。令$m$为二分图的最大匹配的大小。则答案为$n-m$。

构出了二分图之后我们可以构出其最大独立集$I$(怎么构的话英文wiki和上面的网页上都有吧)。对于一个$1\le i\le n$，如果$x(i)\in I$且$y(i)\in I$，那么将$i$加入我们的反链$A$。

首先我们证明$A$的确是个反链。否则的话假设$u\in A,v\in A,u < v$。那么应该存在$x(u)$到$y(v)$的边。而$x(u),y(v)$却是在同一个独立集中的。所以产生矛盾，$A$是反链。

然后我们证明这个反链的大小至少为$n-m$。把独立集中的点称作黑点，其他点称作白点。那么黑点的数目是$2n-m$。而黑点的数目=$|A|$+(满足$x(i)\in I$或$y(i)\in I$的$i$的数目)，后者不会超过$n$，则前者至少是$n-m$。

这样！我们构造出了一个大小至少是$n-m$的反链！然后最小链覆盖的大小就是$n-m$，反链的大小不会超过它，所以这个反链的大小就是$n-m$，且是我们要求的最大反链。

数据、某蒟蒻写的spj、某蒟蒻写的程序 提取密码：tjqs(好像不需要提取密码)

spj可以直接用于lemon。

如果发现程序或spj有错请在下方评论或私信r_64。