把父亲→儿子的辈分关系建为 DAG 的有向边，用 Kahn 拓扑排序输出一个合法辈分序列。
OJ: roj
题目 ID: 1351
难度:入门
标签:拓扑排序图论DAG
创建: 2026-09-30 06:34
更新: 2026-10-05 11:23
题目描述
给出每个人（编号 1~N）的儿子列表，每行以 0 结束。要求输出一个序列，使每个人的所有后辈都比他本人后出现；多解时任意输出一个。
思路
把“父亲→儿子”的辈分关系建为 DAG 的有向边，对 DAG 做 Kahn 拓扑排序：每次输出入度为 0 的节点，并将其儿子的入度减 1。
参考代码
Python 版：
python
#!/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-07-08 10:30
# update_at: 2026-07-08 10:30
import sys
from collections import deque
def topological_sort(n: int, children: list[list[int]]) -> list[int]:
"""Kahn 拓扑排序：父节点必须排在所有后代之前。"""
indeg = [0] * (n + 1)
for u in range(1, n + 1):
for v in children[u]:
indeg[v] += 1
q = deque(u for u in range(1, n + 1) if indeg[u] == 0)
order: list[int] = []
while q:
u = q.popleft()
order.append(u)
for v in children[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
children: list[list[int]] = [[] for _ in range(n + 1)]
for u in range(1, n + 1):
while (v := next(data)) != 0:
children[u].append(v)
print(' '.join(map(str, topological_sort(n, children))))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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-05 11:23
* update_at: 2026-10-05 11:23
*/
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN = 105; // 家族人数上限
int n; // 家族人数
vector<int> g[MAXN]; // 邻接表，g[u] 存 u 的儿子
int in_deg[MAXN]; // 每个节点的入度
queue<int> q; // Kahn 拓扑排序用的队列
int ans[MAXN]; // 拓扑序结果
int ans_len; // 结果长度
// 读入第 u 个人的儿子列表，建边并统计入度
void read_input() {
scanf("%d", &n);
for (int u = 1; u <= n; u++) {
int v;
while (scanf("%d", &v) == 1 && v != 0) {
g[u].push_back(v); // u 是 v 的父亲，建边 u -> v
in_deg[v]++; // v 的入度加 1
}
}
}
// Kahn 拓扑排序：每次输出入度为 0 的节点
void solve() {
for (int u = 1; u <= n; u++) {
if (in_deg[u] == 0) {
q.push(u);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
ans[++ans_len] = u;
// 把 u 的所有儿子 v 的入度减 1，入度变为 0 就入队
for (int i = 0; i < (int)g[u].size(); i++) {
int v = g[u][i];
in_deg[v]--;
if (in_deg[v] == 0) {
q.push(v);
}
}
}
}
int main() {
read_input();
solve();
for (int i = 1; i <= ans_len; i++) {
if (i > 1) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
return 0;
}