K(1≤K≤100)只奶牛分散在N(1≤N≤1000)个牧场.现在她们要集中起来进餐.牧场之间有M(1≤M≤10000)条有向路连接,而且不存在起点和终点相同的有向路.她们进餐的地点必须是所有奶牛都可到达的地方.那么,有多少这样的牧场呢?
第1行输入K,N,M.接下来K行,每行一个整数表示一只奶牛所在的牧场编号.接下来M行,每行两个整数,表示一条有向路的起点和终点
2 4 4 2 3 1 2 1 4 2 3 3 4
sample output:
2
牧场3,4是这样的牧场.
AC——code:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
/* 整体思路:从每个奶牛所在的地方开始访问,每个节点若能被访问到,则对应的次数+1,如果某个节点次数为奶牛数,
则符合题目要求 */
struct nds{
int y;
int nxt;
};
struct edg{ //输入时,存边用
int x;
int y;
};
nds e[10005];
edg a[10005];
int lk[1005],sum;
int k,n,m,ltp;
int t1[105];
int f[1005];
int h[1005];//每次处理f数组结果时用
void ist(int x,int y){
e[++ltp]={y,lk[x]};
lk[x]=ltp;
}
void dfs(int x){
if(f[x]) return ;
f[x]=true;
for(int i=lk[x];i;i=e[i].nxt){
dfs(e[i].y);
}
}
void fun(){
for(int i=1;i<=n;i++){
if(f[i])
h[i]++;
}
}
int main(){
cin>>k>>n>>m;
for(int i=1;i<=k;i++){
cin>>t1[i];
}
for(int i=1;i<=m;i++){
cin>>a[i].x;
cin>>a[i].y;
}
for(int i=1;i<=m;i++){
ist(a[i].x,a[i].y);
}
for(int i=1;i<=k;i++){
if(t1[i]){
dfs(t1[i]);
fun();
for(int i=1;i<1005;i++)
f[i]=false;
}
}
int p;
for(int i=1;i<=1005;i++){
if(h[i]==k){
sum++;
}
}
cout<<sum;
cin>>p;
return 0;
}