84 lines
2.2 KiB
C++
84 lines
2.2 KiB
C++
#include <cstring>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
class Graph {
|
|
public:
|
|
struct Edge {
|
|
int target_vertex = -1;
|
|
int next_edge = -1;
|
|
};
|
|
|
|
vector<int> head_edges;
|
|
vector<Edge> edges;
|
|
|
|
explicit Graph(int vertices_amount = 0, int edges_amount = 0) : head_edges(vertices_amount, -1) {
|
|
edges.reserve(edges_amount);
|
|
}
|
|
|
|
void init(int vertices_amount, int edges_amount) {
|
|
head_edges.resize(vertices_amount, -1);
|
|
edges.reserve(edges_amount);
|
|
}
|
|
|
|
void add_edge(int source_vertex, int target_vertex) {
|
|
edges.push_back({target_vertex, head_edges[source_vertex]});
|
|
head_edges[source_vertex] = static_cast<int>(edges.size()) - 1;
|
|
}
|
|
};
|
|
|
|
constexpr int MAX_V = 1e3 + 5;
|
|
|
|
int cows_amount, vertices_amount, edges_amount, ans;
|
|
vector<int> cows_locations;
|
|
Graph graph;
|
|
|
|
bool vis[MAX_V];
|
|
int vertices_accessibility[MAX_V];
|
|
|
|
void dfs(int start_vertex, int current_vertex) {
|
|
if (vis[current_vertex]) { return; }
|
|
vis[current_vertex] = true;
|
|
vertices_accessibility[current_vertex]++;
|
|
for (int edge = graph.head_edges[current_vertex]; edge != -1; edge = graph.edges[edge].next_edge) {
|
|
int next_vertex = graph.edges[edge].target_vertex;
|
|
dfs(start_vertex, next_vertex);
|
|
}
|
|
}
|
|
|
|
void dfs(int start_vertex) {
|
|
memset(vis, false, sizeof(vis));
|
|
dfs(start_vertex, start_vertex);
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
cin >> cows_amount >> vertices_amount >> edges_amount;
|
|
cows_locations.resize(cows_amount);
|
|
graph.init(vertices_amount, edges_amount);
|
|
for (int i = 0; i < cows_amount; i++) {
|
|
cin >> cows_locations[i], cows_locations[i]--;
|
|
}
|
|
for (int i = 0; i < edges_amount; i++) {
|
|
int source_vertex, target_vertex;
|
|
cin >> source_vertex >> target_vertex, source_vertex--, target_vertex--;
|
|
graph.add_edge(source_vertex, target_vertex);
|
|
}
|
|
|
|
for (const int cow : cows_locations) {
|
|
dfs(cow);
|
|
}
|
|
for (int i = 0; i < vertices_amount; i++) {
|
|
if (vertices_accessibility[i] == cows_amount) {
|
|
ans++;
|
|
}
|
|
}
|
|
cout << ans << endl;
|
|
|
|
return 0;
|
|
}
|