3045: 【普及/提高-】【P2853】Cow Picnic S
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：7
解决：2
题目描述
只奶牛分散在 个牧场．现在她们要集中起来进餐。牧场之间有 条有向路连接，而且不存在起点和终点相同的有向路．她们进餐的地点必须是所有奶牛都可到达的地方。那么，有多少这样的牧场可供进食呢？
输入
Line 1: Three space-separated integers, respectively: K, N, and M
Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.
Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.
输出
Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.
样例输入 复制
2 4 4
2
3
1 2
1 4
2 3
3 4样例输出 复制
2提示
#include<bits/stdc++.h>
using namespace std;
#define MAXK 110
#define MAXN 1010
vector <int> p[MAXN];
bool u[MAXN];
int k,n,m,ans=0,f[MAXN],a[MAXK];
void dfs(int x) {
for (int i = 0, sz = p[x].size(); i < sz ; i++) {
if (!u[p[x][i]]) {
u[p[x][i]] = true;
f[p[x][i]]++;
dfs(p[x][i]);
}
}
}
void bfs(int x) {
queue<int> q;
q.push(x);
while(!q.empty()) {
x=q.front();
q.pop();
for (int i = 0, sz = p[x].size(); i < sz ; i++) {
if (!u[p[x][i]]) {
u[p[x][i]] = true;
f[p[x][i]]++;
q.push(p[x][i]);
}
}
}
}
int main(){
cin >> k >> n >> m;
for (int i = 1; i <= k; i++) cin >> a[i];
for (int i = 1; i <= m; i++) {
int x,y;
cin >> x >> y;
p[x].push_back(y);
}
for (int i = 1; i <= k; i++) {
memset(u,0,sizeof(u));
u[a[i]] = true;
f[a[i]]++;
bfs(a[i]);
}
for (int i = 1; i<=n ; i++)
if (f[i] == k ) ans++;
cout << ans << endl;
return 0;
}