一个网站主机多少钱一年/seo排名赚下载

题意：给定一个有向无环图，可以按照路径方向行走，问最少从几个起点开始行走能走完整个图。

思路：二分图最大匹配。答案为节点数减去最大匹配数。

#include <stdio.h>
#include <string.h>
#define N 125
int n,m,T;
int g[N][N],link[N],visited[N];
int dfs(int i){int j;for(j = 1;j<=n;j++)if(g[i][j] && !visited[j]){visited[j] = 1;if(link[j] == -1 || dfs(link[j])){link[j] = i;return 1;}}return 0;
}
int hungary(){int i,res=0;memset(link,-1,sizeof(link));for(i = 1;i<=n;i++){memset(visited,0,sizeof(visited));if(dfs(i))res++;}return res;
}
int main(){freopen("a.txt","r",stdin);scanf("%d",&T);while(T--){int i,j,a,b;memset(g,0,sizeof(g));scanf("%d %d",&n,&m);while(m--){scanf("%d %d",&a,&b);g[a][b] = 1;}printf("%d\n",n-hungary());}return 0;
}