#B3644. 【模板】拓扑排序 / 家谱树(Topological Sort Family Tree)
0
【模板】拓扑排序 / 家谱树(Topological Sort Family Tree)
【模板】拓扑排序 / 家谱树(Topological Sort Family Tree)
题目描述
有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列,使得每个人的后辈都比那个人后列出。
输入格式
第 行一个整数 (),表示家族的人数。接下来 行,第 行描述第 个人的后代编号 ,表示 是 的后代。每行最后是 表示描述完毕。
输出格式
输出一个序列,使得每个人的后辈都比那个人后列出。如果有多种不同的序列,输出任意一种即可。
样例输入 #1
5
0
4 5 1 0
1 0
5 3 0
3 0
样例输出 #1
2 4 5 3 1
数据范围
对于 的数据,,保证辈分关系构成有向无环图。
知识点与难度
本题涉及的知识点从属于 CSP-J,难度(CF Rating):1200。
测试点分布
| Subtask | 分值 | 测试点编号 | 说明 |
|---|---|---|---|
| 0 | 10 | 1 | 样例 |
| 1 | 20 | 2~7 | 小规模 N≤10 / 特殊: N=1单人家族 / 特殊: 完全无边独立森林 |
| 2 | 8~13 | 中等规模 N≤50 / Hack: 逆编号单链(N→N-1→...→1)与重边 | |
| 3 | 30 | 14~20 | 满规模 N=100 稠密完全DAG拓扑排序压力测试 |
| 4 | 20 | 21~25 | 满规模 N=100 随机分层家族树综合回归 |
出处:原题链接