1、 拓扑排序

我们起床穿裤子和鞋子时，相信大部分人的顺序是这样的，先穿上内裤，然后再穿上裤子，再穿上袜子，然后才是鞋子。  那么 ，我们把这些步骤分解：

(1)穿内裤

(2)穿裤子

(3)穿袜子

(4)穿鞋子

我们把这四个步骤，按照上述的顺序 给排一下， 这就是所谓的拓扑排序 。

当然这个排序的顺序是 唯一 的，如果你先进行(2)然后(1)(3)(4)，哦，不，你不是超人，请不要这样做， 又假如你按照(1)(2)(4)(3)， 那显然也是不行的。

拓扑排序 也可以描述一个 暑假写作业 的过程 ： 语文作业，数学作业，英语作业，生物作业，化学作业，物理作业。

(1)  语文

(2)  数学

(3)  英语

(4)  生物

(5)  化学

(6)  物理

你可以是(1)(2)(3)(4)(5)(6),也可以是(6)(5)(4)(3)(2)(1)，再者英语老师比较凶，那么可以是(3)(1)(2)(4)(5)(6)。等等其他的排序方式。

那么这个排序又是 不唯一 的。

因此  拓扑排序可能是唯一的又有可能是不唯一的。

就像 3个篮球队进行比赛。  编号分别为 1  ， 2 ， 3。

1打赢了2

2打赢了3

3打赢了1。 问谁是最后的冠军。 各一胜一负你问我谁是冠军 ，这不是扯蛋嘛。 So，这是不能判断谁是冠军的，  因为这个事件存在一个 环，互相牵制，进行排序是不行产生结果的。

如果这样  ：

1打赢了2

3打赢了2

那么最后的冠军可能是不确定的，因为你不知道1和3 谁强。 所以只能是 1,3并列了，你如果喜欢大数在前 那就是3 1 2，反之，就是1 3 2了。

拓扑排序其实就是这个样子。

前面大篇幅的扯犊子，主要是介绍什么是拓扑排序。 那么我们要讨论一下，怎么样进行拓扑排序呢？  哎，这个问题好！

插播 ：

我们再次的从 1  2  3  这三支队伍的冠军争夺赛说起。

1打赢了2  因为2输了一场比赛，所以要给2做一标记。因此2号的菊花上就出现了一杆长枪。 我们称这个标记为 入度 那么2的入度就是 1了。

3打赢了2   因为2又输了一场比赛，又是一杆长枪啊。为什么受伤的总是2。  那么2的入度 就++了  变成 了2。

好了  这就是 什么是  入度  了。  如果你还不是很懂 入度是什么 。那我告诉你， 入度 在这里就是2号被打败了几次 。

那我们 就要 进入正题了。

拓扑排序 ：

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。 （摘自 ： 百度百科）

我们继续 以题来进行讲解和理解的加深。

1 Description 2 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 3   4  5 Input 6 输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。 7   8  9 Output10 给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。11 12 其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。13  14 15 Sample Input16 17 4 3 18 1 2 19 2 3 20 4 321 22  23 24 Sample Output25 26 1 2 4 3

学习了