小埋养牛之牛吃饭问题，救救我

常规
1

3. 小埋养牛之牛吃饭问题

题目ID：15665必做题100分

时间限制: 1000ms

空间限制: 65536kB

题目描述

小埋最近又在扩展新业务，在养牛，小埋为了方便管理这些牛吃饭的问题，只有这些牛都在一个牧场的时候，小埋才会给牛投喂食物，问小埋可以有几个牧场可以投喂食物。 小埋有 kk 只牛，分布在 nn 个牧场，nn 个牧场之间相互有 mm 条单向边的道路，牛可以通过道路在牧场与牧场之间移动。

输入格式

第一行三个整数 kk，nn，mm 分别代表牛的数量，牧场的数量，以及道路的数量。
接下来 k 个数，分别是 k 只牛所在的牧场编号。
接下来 m 行，每行两个牧场编号 u，v，代表 u 到 v 有一条单向边。

输出格式

输出一个整数，代表小埋能够投喂的牧场数量。

样例

Input 1

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

Output 1

2

样例解释

牛初始在2，3，当它们都在 3 号或者 4 号牧场时，小埋会给牛投喂食物。

数据范围

1<=k<=100
1<=n<=1000
1<=m<=10000

2

先记录每只牛能到达的位置，然后看那些位置能让所有的牛都到达，能让所有的牛都到达的位置数就是答案

3

思路一样，给出两段核心代码：
1.用来搜索

void dfs(int id){
	for(int i=0;i<t[id].size();i++){
		int v=t[id][i];
		if(vis[v]==0){
			vis[v]=1;
			dfs(v);
		}
	}
}

2.用来判断

for(int i=1;i<=k;i++){
		memset(vis,0,sizeof vis);
		vis[w[i]]=1;
		dfs(w[i]);
		for(int i=1;i<=n;i++){
			if(vis[i]) cnt[i]++;
		}
	}
	int maxn=-INT_MAX,ans=0;
	for(int i=1;i<=n;i++){
		if(cnt[i]==k) ans++;
	}
	cout<<ans<<endl;