Dilworth定理：偏序集能划分成的最少的全序集的个数与最大反链的元素个数相等。

证明：

题目让求的是最大反链的长度，因此可以转化为最少能划分成的链的个数。这个问题可以用二分图的最大匹配做。

建立一个二分图，两边都是n个点，原图的每个点 i 对应两个，在左边的叫做 i1, 在右边的叫做 i2 。

然后原图中如果存在一条边 (x, y)，那么就在二分图中建立 (x1, y2) 的边。

这样建立二分图之后，原图的点数 n - 二分图最大匹配 = 原图的最小路径覆盖（路径不能相交）。

这样为什么是对的呢？我们可以认为，开始时原图的每个点都是独立的一条路径，然后我们每次在二分图中选出一条边，就是将两条路径连接成一条路径，答案数就减少1。

因此最大的匹配就对应着减去的路径最多，也就是最少的链。

参考：

要注意的是需要先做一次传递闭包，因为这里的边是具有传递性的，输入给出的所有u v边，还可以推出一些边，这些隐含边也要加进图里。（这样其实是把路径不能相交变成了路径可以相交）

#include
     
      using namespace std;const int MAXN=105;int g[MAXN][MAXN];int uN,vN;int linker[MAXN];bool used[MAXN];bool dfs(int u){    for(int v = 0; v < vN; v++)        if(g[u][v] && !used[v])        {            used[v] = true;            if(linker[v] == -1 || dfs(linker[v]))            {                linker[v] = u;                return true;            }        }    return false;}int hungary(){    int res = 0;    memset(linker,-1,sizeof(linker));    for(int u = 0; u < uN; u++)    {        memset(used,false,sizeof(used));        if(dfs(u))res++;    }    return res;}int main(){    int n,m;    while (~scanf("%d%d",&n,&m))    {        memset(g,0,sizeof(g));        for (int i=1; i<=m; i++)        {            int u,v;            scanf("%d%d",&u,&v);            g[u-1][v-1]=1;        }        for (int k=0; k