OlveraeUNSW
返回题目列表
COMP2521

拓扑排序 · 字典序最小

拓扑排序 · 字典序最小

给一个有向图(边 u v 表示 u 必须排在 v 前面),输出字典序最小的拓扑序。若图中有环(不存在拓扑序),输出 CYCLE。

输入:第一行 V E;接着 E 行 u v(有向边 u → v)。
输出:字典序最小的拓扑序(空格分隔的一行),或 CYCLE。

例:0→1 0→2 1→3 2→3 → 0 1 2 3。

用 Kahn 算法,但把“入度为 0 的待选点”放进最小堆,每次取最小编号——得到字典序最小的序。取出的点数 < V 即有环。

样例

stdin
4 4
0 1
0 2
1 3
2 3
期望输出
0 1 2 3
python3
14