题意:有N个农场,M条路连通他们(只是单向的)
现在有K头牛在一些农场上,
求所有牛能到达的农场个数。
思路:就是对于每头牛单独地DFS,最后逐个检查每个农场牛到的头数。
#include <iostream>
#include<vector>
using namespace std;
int k,n,m;
vector<int> v[1001];
int at[101];
bool b[1001];
int sum[1001];
void dfs(int x)
{
b[x]=true;
int next;
for (int i=0,len=v[x].size();i<len;++i)
{
next=v[x][i];
if (b[next])
continue;
dfs(next);
}
}
int main()
{
int i,j;
cin>>k>>n>>m;
for (i=1;i<=k;i++)
scanf("%d",at+i);
while (m--)
{
scanf("%d%d",&i,&j);
v[i].push_back(j);
}
memset(sum,0,sizeof(sum));
memset(b,false,sizeof(b));
for (i=1;i<=k;++i)
{
dfs(at[i]);
for (j=1;j<=n;++j)
sum[j]+=b[j],b[j]=false;
}
int ans=0;
for (i=1;i<=n;++i)
{
if (sum[i]==k)
ans++;
}
printf("%d\n",ans);
return 0;
}
http://poj.org/problem?id=3256