Cow Picnic S

题目描述：

K(1≤K≤100)只奶牛分散在N(1≤N≤1000)个牧场．现在她们要集中起来进餐．牧场之间有M(1≤M≤10000)条有向路连接，而且不存在起点和终点相同的有向路．她们进餐的地点必须是所有奶牛都可到达的地方．那么，有多少这样的牧场呢？

输入：

第一行三个数，K，N，M

接下来K+1行，每行一个数表示牛所在的牧场

接下来M+1行，每行两个数A,B，表示有一条A到B的有向边

输出：

符合题意的牧场个数

样例输入：

样例输出：

思路：

此题就是先建图，相邻两个农场在一起，再dfs每个农场，此时就需要用到标记数组，如果，此点没被走过，那么将其dfs，那么这个点的所能到的牧场的数量+1，最后再去判断每个牧场，如果这个牧场能与所有牧场联通，就是一个符合条件的牧场。最后输出总量即可。

代码：

#include <bits/stdc++.h>

using namespace std;

int vis[1010];

int k,n,m,ans;

int cow[1010],farm[1010];

vector <int> G[1010];

void dfs(int x)

{

    vis[x]=1;

	cow[x]++;

    for(int i=0;i<G[x].size();i++){

    	if(vis[G[x][i]] == 0){

    		dfs(G[x][i]);

		}

	}

}

int main()

{

    int A,B;

    cin>>k>>n>>m;

    for(int i=1;i<=k;i++) cin>>farm[i];

    for(int i=1;i<=m;i++)

    {

        cin>>A>>B;

        G[A].push_back(B);

    }

    for(int i=1;i<=k;i++) {

		for(int j=1;j<=n;j++){

			vis[j]=0;

		}

		dfs(farm[i]);

	}

    for(int i=1;i<=n;i++){

    	if(cow[i]==k){

    		ans++;

		}

	}

    cout<<ans;

    return 0;

}

巴特西

Cow Picnic S

题目描述：

输入：

输出：

样例输入：

样例输出：

思路：

代码：

最新文章

热门文章