引子：
有一个问题，是对于一个图上的所有点，用不相交的路径把他们覆盖，使得每个点有且仅属于一条路径，且这个路径数量尽量小。
对于这个问题可以把直接有边相连的两点 x —> y，建一个二分图 x' —> y，最后 节点数 - 最大匹配数 即为最终答案。
这才是题解：
但是这个题目不同，此题问的是用一些路径把所有点覆盖，并没有说每个点有且仅属于一条路径，所以需要求这个图的传递闭包。
把可达的两点建立二分图。最后 节点数 - 最大匹配数 即为最终答案。
可以看看这篇blog
——代码
#include <cstdio>
#include <cstring>
#define M(x, a) memset(a, x, sizeof(a)); using namespace std; const int MAXN = ;
int n, m, ans, cnt;
int belong[MAXN];
bool a[MAXN][MAXN], vis[MAXN]; inline bool find(int i)
{
int j;
for(j = ; j <= n; j++)
if(!vis[j] && a[i][j])
{
vis[j] = ;
if(!belong[j] || find(belong[j]))
{
belong[j] = i;
return ;
}
}
return ;
} int main()
{
int i, j, k, x, y;
while(scanf("%d %d", &n, &m) && n + m)
{
ans = ;
M(, a);
M(, belong);
for(i = ; i <= m; i++)
{
scanf("%d %d", &x, &y);
a[x][y] = ;
}
for(k = ; k <= n; k++)
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
a[i][j] = a[i][j] || (a[i][k] && a[k][j]);
for(i = ; i <= n; i++)
{
memset(vis, , sizeof(vis));
if(find(i)) ans++;
}
printf("%d\n", n - ans);
}
}