题目描述
有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列,使得每个人的后辈都比那个人后列出。
输入格式
第 1 行一个整数 N(1≤N≤100),表示家族的人数。接下来 N 行,第 i 行描述第 i 个人的后代编号 ai,j,表示 ai,j 是 i 的后代。每行最后是 0 表示描述完毕。
输出格式
输出一个序列,使得每个人的后辈都比那个人后列出。如果有多种不同的序列,输出任意一种即可。
输入输出样例
输入 #1
5 0 4 5 1 0 1 0 5 3 0 3 0
输出 #1
2 4 5 3 1
上面这道题就是经典的拓扑排序题。
算法过程
拓扑排序的算法过程:
- 找到图中入度为 0 的点;
- 将这个点删除;
- 同时删掉这个点连出去的所有边;
- 重复以上过程直到所有点都被删除。
【入度】指向这个点的边的数量。
我们用画图的方式呈现上述过程。
画图呈现
首先,对于这张图,对其进行拓扑排序:

首先,找到入度为 0 的点,也就是没有边指向它。我们发现是编号为 1 的点,删掉它和它连出去的边。

(循环步骤)再来找入度为 0 的点,是 2 号点,删掉它和它连出去的边。

现在 3 号入度为 0,同理,删掉它和它连向 4 的边。

最后,4 号入度为 0,也被删掉。现在所有点都被删掉了,我们拓扑排序的顺序是什么呢?就是删除这些点的顺序,也就是 1、2、3、4。
【以上即 Kahn 算法,也称'卡恩算法'】
回到例题
回到洛谷 B3644 这道题,我们用拓扑来解决。 拓扑就是来解决这种,有先后的问题。 观察题目,我们不难发现可以这么构图:



