题目：

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

2
1

题目大意：

         一个城市里有n个十字路口。m条街道，要在十字路口上降落伞兵。伞兵可以搜索到降落的那个路口或者沿着此路口所连接的街道搜索到其它路口。使伞兵能找到全部路口，求此时的最小值，即降落伞兵的最小数量

题目分析：

              求有向无环图的最小路径覆盖。

有向无环图的最小路径覆盖 = 节点数 - 最大匹配数。

1、下面时须要用到的一些知识点：

顶点覆盖：

在顶点集合中。选取一部分顶点，这些顶点可以把全部的边都覆盖了。这些点就是顶点覆盖集

最小顶点覆盖：

在全部的顶点覆盖集中，顶点数最小的那个叫最小顶点集合。

独立集：

在全部的顶点中选取一些顶点，这些顶点两两之间没有连线，这些点就叫独立集

最大独立集：

在左右的独立集中，顶点数最多的那个集合

路径覆盖：

在图中找一些路径，这些路径覆盖图中全部的顶点。每一个顶点都仅仅与一条路径相关联。

最小路径覆盖：

在全部的路径覆盖中，路径个数最小的就是最小路径覆盖了。

2、当中至于第一个案例中为什么最小路径覆盖的答案是2，查看一下：http://blog.csdn.net/hjd_love_zzt/article/details/44243725

就知道了。

代码例如以下：

/*
 * c.cpp
 *
 *  Created on: 2015年3月13日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <cstring>


using namespace std;

const int maxn = 121;

int map[maxn][maxn];
int useif[maxn];
int link[maxn];

int n;

bool can(int t){
	int i;
	for(i = 1 ; i <= n ; ++i){
		if(useif[i] == false && map[t][i] == true){
			useif[i] = true;
			if(link[i] == -1 || can(link[i])){
				link[i] = t;

				return true;
			}
		}
	}

	return false;
}


int max_match(){
	int num = 0;

	int i;
	for(i = 1 ; i <= n ; ++i){//须要注意的是,本题中结点序号是从1開始的,而不是从0開始的.所以这里要写成1開始,否则果断的WA
	memset(useif,false,sizeof(useif));
		if(can(i) == true){
			num++;
		}
	}

	return num;
}


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(map,false,sizeof(map));
		memset(link,-1,sizeof(link));


		int m;
		scanf("%d",&n);
		scanf("%d",&m);

		int i;
		for(i = 0 ; i < m ; ++i){
			int a,b;
			scanf("%d %d",&a,&b);
			map[a][b] = true;
		}


		//有向无环图的最小路径覆盖 = 节点数 - 最大匹配数
		printf("%d\n",n- max_match());
	}

	return 0;
}