裸的最小路径覆盖，直接用匈牙利算法即可。一个有向无环图肯定与一个二分图对应，求这个有向无环图的最小路径覆盖就是求对应二分图的最大独立集，所以最后的结果是顶点数n减去最大匹配数m。
//poj1422 by nepNINE#include<iostream>
using namespace std;
const int maxN=128; int M,v1,v2;
bool g[maxN][maxN];
bool vis[maxN];
int link[maxN];bool dfs(int x)
{for(int y=1;y<=v2;++y) if(g[x][y]&&!vis[y]){vis[y]=true;if(link[y]==0||dfs(link[y])){link[y]=x;return true;}}return false;
}void hungary()
{for(int x=1;x<=v1;++x){memset(vis,false,sizeof(vis));if(dfs(x))++M;} return ;
}int main()
{int cases;scanf("%d",&cases);while(cases--){memset(g,0,sizeof(g));memset(link,0,sizeof(link));int n,m;scanf("%d%d",&n,&m); while(m--){int x,y;scanf("%d%d",&x,&y);g[x][y]=1;}M=0;v1=v2=n;hungary();printf("%d\n",n-M);}return 0;
}