P2853 [USACO06DEC] Cow Picnic S
逆向思维
如果顺着题目走，不大好做。
考虑该题要求的是可以供所有奶牛到达的牧场，那么不如从奶牛所在的牧场下手
即对每个奶牛所在的牧场 \(DFS\)，对所有到达点标记。
那么显然当一个点的标记等于 \(k\) 时，说明该牧场是合适的。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
const int N = 1e3 + 10;
const int M = 1e4 + 10;
int k, n, m;
int ans;
int pasture[N];
bool vis[N];
int tag[N];
int tot, head[N];
struct Node {
int to, next;
}edge[M];
void addEdge()
{
int u, v;
std::cin >> u >> v;
edge[++tot].to = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs(int now)
{
vis[now] = true; tag[now]++;
for (int i = head[now]; i; i = edge[i].next)
if (!vis[edge[i].to]) dfs(edge[i].to);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> k >> n >> m;
for (int i = 1; i <= k; i++) std::cin >> pasture[i];
for (int i = 1; i <= m; i++) addEdge();
for (int i = 1; i <= k; i++)
{
memset(vis, 0, sizeof(vis));
dfs(pasture[i]);
}
for (int i = 1; i <= n; i++) ans = (tag[i] == k ? ans + 1 : ans);
std::cout << ans;
return 0;
}