题意:

求出有向图中,所有奶牛在的牧场(点)都能到达的牧场(点)的数量

思路:

一个数组to来计数奶牛去过的牧场次数sum=0

最后统计次数等于奶牛数量的的牧场sum+=1

至于奶牛的寻路要搜索,不会的看这里: 校内点我 校外点我

模拟:

输入:
2 4 4
2
3
1 2
1 4
2 3
3 4
图:
1-->2
↓   ↓
4<--3
to:
0-->0
↓   ↓
0<--0
在牧场2的奶牛搜索完后的to:
0-->1
↓   ↓
1<--1
在牧场3的奶牛搜索完后的to:
0-->1
↓   ↓
2<--2
奶牛有两只,to有两个为奶牛数量的
输出:
2

代码:

#include<iostream>
#include<vector>
using namespace std;
const int N=1e5;
vector<int >g[N];//有向图
bool vis[N]={0};//标记每只奶牛是否走过
int to[N]={0};//计数每只奶牛去过的牧场次数
vector<int >cow;//奶牛
int k,n,m,sum=0;
void dfs(int x)//dfs深度深搜
{
	to[x]+=1;//代表这只牛能走这里
	vis[x]=1;//标记
	for(int i=0;i<g[x].size();i++)//下条路
	{
		if(!vis[g[x][i]])//是否走过
		{
			vis[g[x][i]]=1;//标记
			dfs(g[x][i]);//dfs深度搜索
		}
	}
}
int main()
{
	cin>>k>>n>>m;//输入
	for(int i=0;i<k;i++)
	{
		int x;
		cin>>x;//输入
		cow.push_back(x);//添加奶牛所在的牧场
	}
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;//输入
		g[u].push_back(v);//有向图的做法
	}
	for(int i=0;i<k;i++)
	{
		fill(vis,vis+N,0);//重置标记
		if(!vis[cow[i]])//是否标记过
		{
			dfs(cow[i]);//dfs深度搜索
		}	
	}
	for(int i=0;i<N;i++)
	{
		if(to[i]>=k)//当等于奶牛数量时
		{
			sum++;//添加
		}
	}
	cout<<sum;//输出
	return 0;//完结散花
}

翻译：讨论详情 - ZXOJ

题意

当前有 $K$ 头牛在牧场（编号为 1 到 $N$），每个牧场有单行道相通（共 $M$ 条），求有多少个野餐地

野餐地定义：所以牛都能到的牧场

思路

遍历每头牛能去的牧场，看看有哪些牧场所有牛都能去

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> a[1005];
int c[105],f[1005],cnt;	// c 存当前牛在的牧场，f 记有几头牛能到这个牧场
bool v[1005];
void dfs(int n){
	v[n] = 1;
	f[n]++;	// 这头牛能到这个牧场
	for (int i = 0;i < a[n].size();i++){
		if(!v[a[n][i]])	dfs(a[n][i]);
	}
}
int main(int argc, char **argv){
	int k,n,m;
	cin >> k >> n >> m;
	for (int i = 0;i < k;i++){
		cin >> c[i];
	}
	for (int i = 0;i < m;i++){
		int A,B;
		cin >> A >> B;
		a[A].push_back(B);	// A 通向 B 的单行道
	}
	for (int i = 0;i < k;i++){
		dfs(c[i]);	// 这头牛能到哪些牧场
		memset(v,0,sizeof(v));	// 重置
	}
	for(int i = 1;i <= n;i++){
		if (f[i] == k)	cnt++;	// 如果所有牛都能到，就把能野餐的地方加 1
	}
	cout << cnt;
	return 0;
}