问题 C: 课程学习顺序安排

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:6 解决:4

题目描述

现在你总共有 n 门课程需要学习,课程编号为 0 到 n-1。给你一个数组 prerequisites,其中 prerequisites[i] = [a, b],表示在学习课程 a 之前必须先完成课程 b。 例如,想要学习课程 0,你需要先完成课程 1,我们用一个匹配来表示:[0,1]。 你的任务是找出一个合理的学习顺序,使得能够学完所有课程。可能会有多个正确的顺序,你只需要输出任意一种即可。如果不可能完成所有课程(存在循环依赖),输出 "IMPOSSIBLE"。

输入

第一行包含两个整数 n 和 m,分别表示课程总数和先修关系总数。 接下来 m 行,每行包含两个整数 a 和 b,表示学习课程 a 之前必须先完成课程 b。

输出

如果存在合理的学习顺序,输出 n 个整数,表示课程的学习顺序(用空格分隔)。 如果不存在合理的学习顺序,输出 "IMPOSSIBLE"。

样例输入 复制

4 4
1 0
2 0
3 1
3 2

样例输出 复制

0 1 2 3

提示

解释: 总共有 4 门课程。要学习课程 3,需要先完成课程 1 和课程 2。而课程 1 和课程 2 都需要在课程 0 之后学习。因此,一个正确的学习顺序是 0 -> 1 -> 2 -> 3。 1 ≤ n ≤ 2000 0 ≤ m ≤ n × (n-1) 0 ≤ a, b