Cow Picnic(DFS)

リンク:http://poj.org/problem?id=3256
Cow Picnic
Time Limit: 2000 MS
 
メモリLimit: 65536 K
Total Submissions: 5128
 
Acceepted: 2112
Description
The cows are having a picnic！Each of Farmer John's K （1≦ K ≦100）cows is grazing in one of N （1≦ N ≦1,000）pastures、convently numberd 1…N.The pastures are connected by M （1≦ M ≤10,000)one-way paths(ノpath connects a pasture to itself)
The cows Want to gather in the same pasture for their picnic，but(because of the one-way paths)some cows may only be able to some pastures.Help the cows out byfigling out howmay paths)some parenice
Input
Line 1:Three space-separated integers，repectively: 
Kです。 
N，and 
M 
Lines 2.
K+1:Line 
i＋1 contains a single integer(1.
N）which is the number of the pasture in which cow 
i is grazing. 
リンス 
K+2.
M+
K+1:Each line contains two space-separated integers，repectively 
A and 
B （both 1.
N and 
A != 
B)representing a one-way path from pasture 
A to pasture 
B.
Output
Line 1:The single integer that is the number of pastures that are reachable by all cows via the one-way paths.
Sample Input

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

Sample Output

2

ベント
The cows can meet in pastures 3 or 4.
ソurce
USACO 2006 December Silver
AC コード:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define MAXN 20020
#define INF 9999999999
using namespace std;
int k,n,m;
vector<int>map[MAXN];
int cow[MAXN];
bool vis[MAXN];
int cnt[MAXN];
void dfs(int n)
{
	cnt[n]++;
	vis[n]=true;
	for(int i=0;i<map[n].size();i++)
	{
		if(!vis[map[n][i]])
		dfs(map[n][i]);
	}
}

int main()
{
	int u,v,ans;
	while(cin>>k>>n>>m)
	{
		for(int i=1;i<=k;i++)
		{
			cin>>cow[i];
		}
		while(m--)
		{
			cin>>u>>v;
			map[u].push_back(v);
		}
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=k;i++)
		{
			memset(vis,false,sizeof(vis));
			dfs(cow[i]);
		}
		ans=0;
		for(int i=1;i<=n;i++)
		{
			if(cnt[i]==k)
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}