Problem 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, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no 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 get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

Input

Line 1: Three space-separated integers, respectively: 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.?

Lines K+2..M+K+1: Each line contains two space-separated integers, respectively 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

題意：k 頭牛，n 個(gè)牧場(chǎng)，m 條單向的路，求所有牛能到達(dá)的牧場(chǎng)數(shù)

思路：對(duì)每頭牛進(jìn)行 dfs 搜索，最后統(tǒng)計(jì)每個(gè)農(nóng)場(chǎng)到達(dá)的牛數(shù)。

Source Program

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 10001 #define MOD 123 #define E 1e-6 using namespace std; int k,n,m; int cow[N]; int sum[N]; int vis[N]; vector<int> g[N]; void dfs(int i) {vis[i]=1;//標(biāo)記為已到達(dá)int len=g[i].size();//從當(dāng)前牧場(chǎng)可到達(dá)其他牧場(chǎng)的個(gè)數(shù)for(int j=0;j<len;j++)//枚舉所有可到達(dá)的牧場(chǎng){int next=g[i][j];if(!vis[next])//如果下一個(gè)牧場(chǎng)未到達(dá)，繼續(xù)向下搜索dfs(next);} } int main() {scanf("%d%d%d",&k,&n,&m);for(int i=1;i<=k;i++)scanf("%d",&cow[i]);while(m--)//vector鄰接表建圖{int x,y;scanf("%d%d",&x,&y);g[x].push_back(y);}for(int i=1;i<=k;i++){dfs(cow[i]);//dfs每一頭牛for(int j=1;j<=n;j++)//統(tǒng)計(jì)每一個(gè)牧場(chǎng)的到達(dá)數(shù){sum[j]+=vis[j];vis[j]=0;}}int cnt=0;for(int i=1;i<=n;i++)//枚舉所有牧場(chǎng)if(sum[i]==k)//如果該牧場(chǎng)所有牛均能到達(dá)cnt++;printf("%d\n",cnt);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Cow Picnic（POJ-3256）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。