POJ 3256 （简单的DFS)

//题意是 K N, M;

//有K个牛 N个牧场，M条路，有向的

//把K个牛放到任意的n个不同牧场中，问所有牛都可以到达的牧场数的总和

//这是一道简单的DFS题

//k 100

//n 1000

//m 10000

#include <iostream>

#include <cstdio>

#include <vector>

#include <cstring>

using namespace std;

int k, n, m;

int a[105];

int book[1005], sum[1005];

vector<int> map[1005];

void dfs( int x ) {
sum[x]++;
for(int i = 0;i<map[x].size();i++){
int v = map[x][i];
if(book[v]==0){
book[v] = 1;
dfs(v);
}
}
return;

}

int main()

{

while(~scanf("%d%d%d",&k,&n,&m)){

for( int i = 1; i <= k ; i++ ) {
scanf("%d",&a[i]);
}

for(int i=1;i<=m;i++){
int a, b;
scanf("%d%d",&a,&b);
map[a].push_back(b);
}
memset(sum,0,sizeof(sum));
for(int i = 1;i <= k; i++ ) {
memset( book, 0, sizeof(book) );
book[a[i]] = 1;
dfs( a[i] );
}
int ans = 0;
for(int i=1;i<=n;i++){
if(sum[i]==k) ans++;

// cout<<" i = "<<i<<" sum [i] "<<sum[i]<<endl;
}
cout<<ans<<endl;
}

return 0;

}

巴特西

POJ 3256 （简单的DFS)

最新文章

热门文章