通道忽略方向后是树,有向定向必有终点,答案即出度为 0 的唯一加工站,多于一个就无解。
OJ: roj
题目 ID: 2126
难度:普及-
标签:图论树出度python
创建: 2026-10-08 07:42
更新: 2026-10-08 07:42
形式化题目
给定
定义可达关系
以题面样例为例,
正解
思路
最直接的判定是:反向建图(把
关键在于观察路径的终点:
- 由于底图是树、边数是
, 里不可能出现有向环(有向环要求底图有环)。于是在这个有限的有向无环图上,从任意站 出发顺着出边一直走,路径只可能一路延伸或者停在某个出度为 0 的站,不会绕圈,必然终止。 - 设
是出度为 0 的站。它没有任何出边,所以从 出发只能到达它自己。若要 ,就必须 。也就是说:任何出度为 0 的站,一旦答案存在,答案只能是它本身。
两条观察合起来给出充要条件:
| 出度为 0 的站数 | 结论 |
|---|---|
| 取其中两个 |
|
| 从任意 |
于是**「答案存在」等价于「出度为 0 的站恰好一个」,且该站即为答案**。值得注意的是答案天然唯一:若两个站
细看这条判定为什么必须依赖树性:对一般有向图,「唯一出度为 0 的点」只是必要条件。例如边集
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:42
# update_at: 2026-10-08 07:42
import sys
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
# 通道忽略方向是最少的 N-1 条 ⇒ 底图是树,有向定向不可能有环,
# 每个站顺着出边走必然停在出度为 0 的站(sink)。
edges = [(next(data), next(data)) for _ in range(n - 1)]
sinks = set(range(1, n + 1)) - {start for start, _end in edges} # 出度为 0 的站
sink_count = len(sinks)
# sink 多于一个 ⇒ 谁也到不了别的 sink;恰好一个 ⇒ 全图都汇入它,它即答案
print(min(sinks) if sink_count == 1 else -1)
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 07:42
* update_at: 2026-10-08 07:42
*/
// [USACO19OPEN] Milk Factory
// 题意:N 个加工站、N-1 条单向传送带 a -> b,且这些通道是用最少数量把所有站连起来的,
// 所以忽略方向后是一棵连通无环的树。求最小的 i,使得从其他每个站出发沿单向边
// (可经过中间站)都能到达 i;不存在则输出 -1。
// 做法:树的有向定向不可能出现有向环,所以从任意站顺着出边一直走必然停在某个出度为 0
// 的站(sink)。若出度为 0 的站超过 1 个,任何一个 sink 都到不了别的 sink,无解;
// 若恰好一个,则所有站的路径都只能终止于它,它就是答案。故答案 = 唯一的 sink。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 105;
int out_degree[MAXN]; // out_degree[i]:从 i 出发的传送带条数
int main() {
int n;
if (scanf("%d", &n) != 1) return 0; // 保证 1 <= N <= 100
for (int k = 1; k <= n - 1; ++k) {
int a, b;
scanf("%d %d", &a, &b); // 传送带 a -> b,只有出发站 a 的出度增加
out_degree[a]++;
}
int sink_count = 0; // 出度为 0 的站(路径终点)个数
int answer = -1;
for (int i = 1; i <= n; ++i) { // 升序扫描,顺便保证答案取最小
if (out_degree[i] == 0) {
sink_count++;
answer = i;
}
}
if (sink_count == 1) {
printf("%d\n", answer);
} else {
printf("-1\n");
}
return 0;
}复杂度
时间
总结
这道题的关键不是「可达性」,而是「可达性在树的有向定向下退化成什么」。有向环不存在,所以每条路都有终点;终点的出度为 0,所以终点只能是自己;出度为 0 的站一旦多于一个就谁也到不了谁。三步推理把
实现上的两个坑:一是边的方向,输入「从
数据说明:本题素材由带数据生成脚本的仓库提供(10 组数据由脚本按分层结构构造,非 USACO 官方数据),题面为网络重建版本。生成脚本断言每组数据的底图都是树,本解法的成立依赖该性质。