有向无环图的拓扑排序
Special Judge
提交数: 34, 通过率: 29.41%, 平均分: 33.24
题目描述:
由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。
拓扑排序是对有向无环图( DAG）的顶点进行线性排序的一种算法，使得对于从顶点 u 到顶点 v 的每条有向边 uv，u 在排序中都出现在 v 之前。这种排序在计算机科学领域中非常重要，尤其是在任务调度、课程安排等场景中。
现读入一个有向图（若干条有向边），建立有向图并判断此图是否有回路，如果没有回路则输出任意一个拓扑序列。
输入格式:
输入的第一行包含两个正整数n和m，表示图中共有 n 个顶点，m 条有向边。其中 \( n \le 100000，m \le 200000 \) 。
以后的 m 行中每行有两个用空格隔开的整数 \( i \) 和 \( j \) ，表示第i个顶点有指向第j个顶点的有向边。
输出格式:
如果读入的有向图含有回路，请输出“ERROR”，不包括引号。
如果读入的有向图不含有回路，输出图的一个拓扑序列，每个整数后输出一个空格。
样例输入:
4 3 1 2 2 3 4 3
样例输出:
4 1 2 3时间限制: 1000ms
空间限制: 256MB