返回题目列表
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