55 lines
1.8 KiB
C++
55 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 10010; //10000条边
|
||
|
||
queue<int> q;
|
||
|
||
bool st[N]; //走过了没
|
||
int n; //n个牧场
|
||
int m; //m条有向路连接
|
||
int K; //k只奶牛
|
||
int a[N]; //记录第i个奶牛在a[i]这个牧场里
|
||
int sum[N]; //记录每个结点被bfs遍历到的次数
|
||
int g[N][N]; //邻接矩阵
|
||
int ans;
|
||
|
||
int main() {
|
||
//k:奶牛数，n:牧场数,m:路线数
|
||
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;
|
||
g[x][y] = 1;//读入m条路径，建图,x->y有一条边
|
||
}
|
||
//从每个奶牛所在的牧场出发
|
||
for (int i = 1; i <= k; i++) {
|
||
//清空状态标识
|
||
memset(st, 0, sizeof(st));
|
||
//将第i个奶牛所在的第a[i]个牧场放入队列
|
||
q.push(a[i]);
|
||
//标识这个牧场已使用过，防止走回头路
|
||
st[a[i]] = true;
|
||
//广度优先搜索
|
||
while (!q.empty()) {
|
||
int x = q.front();
|
||
q.pop();
|
||
//邻接矩阵的遍历
|
||
for (int i = 1; i <= n; i++)
|
||
if (g[x][i] && !st[i]) {
|
||
st[i] = true;//标识为已使用
|
||
q.push(i); //入队列
|
||
}
|
||
}
|
||
//记录每个结点被遍历到的次数
|
||
for (int j = 1; j <= n; j++) sum[j] += st[j];
|
||
}
|
||
//如果n个结点中，存在遍历次数等于k的结点，就是表示k个奶牛都可以到达这个位置
|
||
for (int i = 1; i <= n; i++)
|
||
if (sum[i] == k) ans++;
|
||
//输出结果
|
||
printf("%d", ans);
|
||
return 0;
|
||
} |