61 lines
1.7 KiB
C++
61 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 1010 * 1010; //牧场数上限，这里不算上乘积，就会有3个WA点，
|
||
// 原因很简单，装不下！！这是边的数量上限，要注意，邻接表没有这个问题，一定要区别好！
|
||
|
||
int n; //n个牧场
|
||
int m; //m条有向路连接
|
||
int K; //k只奶牛
|
||
int ans; //ans为最终答案
|
||
int a[N]; //a数组存储牛的位置
|
||
int sum[N]; //sum数组为每个点被遍历的次数
|
||
bool st[N]; //st数组用来判断点是否已经被访问过
|
||
|
||
//链式前向星建图
|
||
int idx, head[N];
|
||
struct Edge {
|
||
int to, next;
|
||
} edge[N];
|
||
|
||
int add_edge(int from, int to) {
|
||
edge[++idx].to = to;
|
||
edge[idx].next = head[from];
|
||
head[from] = idx;
|
||
}
|
||
|
||
//进行图的深度优先遍历
|
||
void dfs(int x) {
|
||
st[x] = true;
|
||
sum[x]++; //将这个点遍历的次数+1
|
||
//枚举节点编号
|
||
for (int i = head[x]; i; i = edge[i].next) {
|
||
int v = edge[i].to;
|
||
if (!st[v]) dfs(v);//就遍历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;
|
||
add_edge(x, y);
|
||
}
|
||
|
||
//对奶牛的位置进行枚举
|
||
for (int i = 1; i <= k; i++) {
|
||
memset(st, 0, sizeof st);
|
||
dfs(a[i]); //从每一只奶牛的位置开始遍历
|
||
}
|
||
|
||
//统计答案，如果当前节点被访问的次数恰好为奶牛的只数
|
||
for (int i = 1; i <= n; i++) if (sum[i] == k) ans++;
|
||
//输出最后答案
|
||
cout << ans << endl;
|
||
return 0;
|
||
} |