从每头牛的起点分别搜索，用计数数组统计被全部搜索到的牧场。
OJ: luogu
题目 ID: P2853
难度:普及-
标签:有向图DFS可达性python
日期: 2026-07-16 18:42
题意
有 k 头牛、n 个牧场和 m 条单向路。每头牛各自在一个牧场，求有多少个牧场能被所有牛到达。
思路
数据范围允许从每头牛的起点各做一次图搜索。
第 i 次搜索中，每到达牧场 v，令 reachable_count[v]+=1。全部搜索结束后，计数等于 k 的牧场就是所有牛可达集合的交集。
每次搜索必须有独立的 visited，保证同一头牛不会因为不同路径重复给一个牧场计数。
Python 知识
bytearray(n+1)是紧凑的 0/1 访问标记数组。- 普通列表的
append/pop可直接作为后进先出栈。 reachable_count.count(k)直接统计值恰好为牛数量的牧场个数。- 批量整数输入后用切片取得所有起点，再用指针读取边。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：图搜索状态与访问标记。/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：容器选择和计数。
代码
python
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
cow_count, n, m = data[:3]
starts = data[3:3 + cow_count]
graph = [[] for _ in range(n + 1)]
pos = 3 + cow_count
for _ in range(m):
u, v = data[pos], data[pos + 1]
pos += 2
graph[u].append(v)
reachable_count = [0] * (n + 1)
for start in starts:
visited = bytearray(n + 1)
visited[start] = 1
stack = [start]
while stack:
node = stack.pop()
reachable_count[node] += 1
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = 1
stack.append(neighbor)
print(reachable_count.count(cow_count))
if __name__ == "__main__":
main()cpp
/**
* P2853 [USACO06DEC] Cow Picnic S
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int MAXM = 10005;
int head[MAXN], to[MAXM], nxt[MAXM], cnt;
int k, n, m;
void add_edge(int u, int v) {
++cnt;
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
bool vis[MAXN];
int reach[MAXN]; // 每个牧场被多少头牛到达
void dfs(int u) {
vis[u] = true;
++reach[u];
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (!vis[v]) dfs(v);
}
}
int main() {
scanf("%d%d%d", &k, &n, &m);
int cows[MAXN];
for (int i = 1; i <= k; ++i) scanf("%d", &cows[i]);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
}
for (int i = 1; i <= k; ++i) {
memset(vis, 0, sizeof(vis));
dfs(cows[i]);
}
int ans = 0;
for (int i = 1; i <= n; ++i)
if (reach[i] == k) ++ans;
printf("%d\n", ans);
return 0;
}复杂度
每头牛搜索一次，时间复杂度
总结
“所有起点都能到达”的交集，可以转成“每个起点各投一票”。最终票数等于起点数的节点就是答案。