Dilworth 定理、Mirsky 定理与 DAG 覆盖
本文给出偏序版本、二分图算法和传递闭包边界；纸质速查见 Dilworth 模板 。
设 $(P,\preceq)$ 是有限偏序集。关系 $\preceq$ 满足自反、反对称和传递。严格关系记为
$$
x\prec y
\quad\Longleftrightarrow\quad
x\preceq y\text{ 且 }x\ne y.
$$
链 ：其中任意两个元素都可比。
反链 ：其中任意两个不同元素都不可比。
链划分 ：把 $P$ 的每个元素恰好放入一条链。
反链划分 ：把 $P$ 的每个元素恰好放入一条反链。
宽度 $\operatorname{width}(P)$ ：最大反链大小。
高度 $\operatorname{height}(P)$ ：最大链大小。
这里“划分”要求各组互不重叠并覆盖全部元素，不是允许重复使用元素的普通覆盖。
Dilworth 定理。 对任意有限偏序集，
$$
\operatorname{width}(P) \text{最少链划分数}.
$$
一条反链中的元素两两不可比，所以同一条链至多包含其中一个元素。因此，若最大反链大小为 $w$ ，任意链划分至少需要 $w$ 条链。定理的实质是总能构造恰好 $w$ 条链。
建立二分图 $B=(L,R,E)$ ：
$L$ 、$R$ 各放一份 $P$ 的元素；
对每个严格关系 $x\prec y$ ，加入边 $x_L-y_R$ 。
设二分图最大匹配大小为 $M$ 。则
$$
\text{最少链划分数}=|P|-M.
$$
给定一组链划分，把每条链中相邻的两个元素连成匹配边。一条含 $s$ 个元素的链贡献 $s-1$ 条匹配边；若共有 $k$ 条链，总共得到 $n-k$ 条匹配边。因此最大匹配满足 $M\ge n-k$ ，即 $k\ge n-M$ 。
反过来，一组大小为 $M$ 的匹配使每个元素至多有一个匹配前驱、一个匹配后继。沿匹配关系连接后不会形成环，因为严格偏序不含环，于是得到若干条链。每加入一条匹配边，链的条数减少一，所以最终有 $n-M$ 条链。
结合 Dilworth 定理：
$$
\operatorname{width}(P)=n-M.
$$
从所有未匹配左点出发，沿“未匹配边 $L\to R$ 、匹配边 $R\to L$ ”做交替可达搜索，记所有可达点为 $Z$ 。由 König 定理，
$$
(L\setminus Z)\cup(R\cap Z)
$$
是一组最小点覆盖。一组对应的最大反链为
$$
A={x:x_L\in Z,\ x_R\notin Z}.
$$
DAG 的可达关系定义了偏序：$x\prec y$ 当且仅当存在从 $x$ 到 $y$ 的非空有向路径。
这里有两个不同问题：
DAG 最小不交路径覆盖 ：每条路径必须沿原 DAG 边前进，二分图只加入原边。可达偏序的最少链划分 ：链中相邻选中元素只需可达，二分图必须加入所有可达对，即使用传递闭包。
两者的答案可能不同。考虑五个点和边
$$
a\to b,
\quad c\to b,
\quad b\to d,
\quad b\to e.
$$
只用原边时最大匹配大小为 $2$ ，最小路径覆盖为 $5-2=3$ 。在可达偏序中还有 $a\prec d,a\prec e,c\prec d,c\prec e$ ；例如
$$
{a,b,e},\qquad{c,d}
$$
是两条链，所以最少链划分数为 $2$ 。第二条链使用了可达关系 $c\prec d$ ，对应路径经过的中间点 $b$ 已在另一条链中；这正是只连原边会漏掉的情况。
Mirsky 定理。 对任意有限偏序集，
$$
\operatorname{height}(P) \text{最少反链划分数}.
$$
一条最大链中的元素两两可比，因此每个反链至多取其中一个元素；任意反链划分至少需要 $h=\operatorname{height}(P)$ 组。
定义
$$
d(x)=1+\max_{y\prec x}d(y),
$$
若 $x$ 没有严格前驱则令 $d(x)=1$ 。$d(x)$ 是以 $x$ 结尾的最长链长度，并且
$$
\max_x d(x)=h.
$$
若 $x\prec y$ ，必有 $d(x)<d(y)$ ，所以所有满足同一个 $d(x)$ 值的元素构成反链。按 $d=1,2,\ldots,h$ 分组便得到恰好 $h$ 个反链，从而达到下界。
先确认题目要求的是链/反链划分 ，还是允许路径共享、元素重复的其他覆盖。
明确偏序关系是题目直接给出的比较关系，还是 DAG 的可达关系。
可达偏序做链划分时，需要传递闭包；原 DAG 路径覆盖只用原边。
Dilworth 用最大匹配计算宽度和最少链划分。
Mirsky 用最长链长度计算最少反链划分，按最长链 DP 层数即可构造方案。