下文简述在偏序集上构造最长反链的一种方法。

（实际上就是从 [CTSC2008] 祭祀 的题解区抄来的）。

首先，根据 Dilworth 定理，最长反链等于最小不可重链覆盖。

求最小链覆盖有个经典的拆点二分图做法，就是把每个点拆成两个点 。然后对于原图的边 ，连边 。然后跑二分图最大匹配，一个关于 点的匹配相当于给一个点找前驱，一个关于 点的匹配相当于给一个点找后继。

那么最小链覆盖就是 - 拆点二分图的最大匹配。

接下来，我们尝试从这个匹配中，构造出最长反链。

我们先构造二分图最大独立集。

首先引入最小点覆盖：选出一个最小的点集，使得每条边的两端都有至少一个点被选中。

因为二分图最大独立集等于最小点覆盖的补（因为最小点覆盖不会出现一条边两端都没有点，等价于最大独立集中不会出现一条边两端都有点），这等价于构造最小点覆盖。

而最小点覆盖等于最大匹配。

因为最小点覆盖肯定大于等于最大匹配（匹配边的两端必须至少选一个点），我们接下来给出一种点覆盖使得其大小等于最大匹配。

考虑从右侧的每个非匹配点开始 DFS，右部点只能走非匹配边向左访问，左部点只能走匹配边向右访问。

我们取出左侧被 DFS 到的点和右侧没被 DFS 到的点，就构成了一个点覆盖。

下文证明这是一个合法点覆盖，且大小等于最大匹配：

1. 合法性

   对于右侧被 DFS 到的所有点，与其相邻的左侧点肯定也被 DFS 到了，这个可以根据这个右部点是否有匹配来讨论证明。

   我们取出的是左侧被搜到的和右侧没被搜到的，基于上述事实，每条边都会被覆盖。

2. 大小等于最大匹配

   因为右侧的非匹配点肯定都被搜到了，在右侧选取的一定是匹配点。

   如果一个右侧的匹配点被搜到了，那与其匹配的左部点肯定也被搜到了，那么它的匹配点就会被选上。

   上述两个事实表明：每条匹配边的端点恰好选一个。

   而左侧的非匹配点肯定不会被搜到，因为如果被搜到了，在 DFS 的过程中就会形成一条增广路，与最大匹配矛盾。

我们取最小点覆盖的补就得到了最大独立集。也就是左侧没被 DFS 到的点和右侧被 DFS 到的点。

然后考虑怎么求出最长反链。

我们对于原图所有点 ，取出 与 都在二分图独立集的点，就得到了最长反链。

显然这是一个合法的反链，大小也与 Dilworth 指出的结果相符。

先记下来，以后应该用得上。