10.28
[CTSC2008] 祭祀 / [CodeForces 590E] Birthday
神仙题。根据 Dilworth 定理，最长反链 = 最小不可重链覆盖。
求最小链覆盖可以将每个点 \(i\) 拆成 \(i\) 和 \(i'\) 两个点。
对于求出传递闭包后的偏序关系 \(u<v\)，就将 \(u\) 和 \(v'\) 连边。
跑出该二分图上的最大匹配 \(m\)，则最小链覆盖为 \(n-m\)，即可求出最长反链长度 \(n-m\)。
对于某个点 \(i\)，如果 \(i\) 和 \(i'\) 都在最大独立集中的话，它就在一条可行的最长反链 \(C\) 中。
证明：若有一个点满足 \(j,j'\in C\) 且 \(i>j\)，则不满足最大独立集性质。因此 \(C\) 一定是反链。
若最大匹配为 \(m\)，则最小点覆盖为 \(m\)。则原图上最少有 \(n-m\) 个点在 \(C\) 中。
又因为 \(|C|\le n-m\)，所以 \(C\) 是符合要求的。
对于第三问的话，可以删点，看最长反链长度是否减小。