UVa 10305：Ordering Tasks , 经典的拓扑排序

UVa 10305：Ordering Tasks , 经典的拓扑排序2014-10-11 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1246

题目类型：拓扑排序

题目：

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 <= n <= 100 and m. n is the number of tasks （numbered from 1 to n） and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

5 4

1 2

2 3

1 3

1 5

0 0

Sample Output

1 4 2 5 3

题目大意：

约翰有n个任务要做，不幸的是，这些任务并不是独立的，执行某个任务之前要先执行完其他相关联的任务。

分析与总结：

这题是最基础的拓扑排序。

拓扑排序的定义：对一个有向无环图（Directed Acyclic Graph简称DAG）G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E（G），则u在线性序列中出现在v之前。

以上的定义比较“学术“，简单的说，就是一些事件，某些必须在另外某些发生之前；比如穿袜和穿鞋；再比如大学选课，选修某门课的前提必须先修完其他一些相关连的课程才可以。

所以，拓扑排序在现实生活中有着十分广泛的应用。

这里有一个拓扑排序过程的演示动画，十分直观：

http://www.jcc.jx.cn/xinwen3/news/kj/flash/2009/0426/1302.htm

一般的题目可能会给一些事件，和一些发生次序，来求一个拓扑排序；

URL：http://www.bianceng.cn/Programming/sjjg/201410/45713.htm

对于拓扑排序主要有两种方法。

第一种是贪心的思路，以邻接表为图的存储结构，过程直接模拟上面的演示动画：

a）扫描顶点表，将入度为零的顶点入栈；（ps：这里栈可以使优先队列 and so on。。） b）当栈非空时：输出栈顶元素v，出栈；检查v的出边，将每条出边的终端顶点的入度减1，若该顶点入度为0，入栈； c）当栈空时，若输出的顶点小于顶点数，则说明AOV网有回路，否则拓扑排序完成。