什么是拓扑排序?

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

拓扑排序介绍
拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。
这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！
例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。
在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。
拓扑排序的算法图解
拓扑排序算法的基本步骤：

构造一个队列Q(queue) 和拓扑排序的结果队列T(topological)；
把所有没有依赖顶点的节点放入Q；
当Q还有顶点的时候，执行下面步骤：
3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；
3.2 对n每一个邻接点m(n是起点，m是终点)；
3.2.1 去掉边;
3.2.2 如果m没有依赖顶点，则把m放入Q;
注：顶点A没有依赖顶点，是指不存在以A为终点的边。

以上图为例，来对拓扑排序进行演示。

第1步：将B和C加入到排序结果中。
顶点B和顶点C都是没有依赖顶点，因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储，因此先访问B，再访问C。访问B之后，去掉边和，并将A和D加入到队列Q中。同样的，去掉边和，并将F和G加入到Q中。
(01) 将B加入到排序结果中，然后去掉边和；此时，由于A和D没有依赖顶点，因此并将A和D加入到队列Q中。
(02) 将C加入到排序结果中，然后去掉边和；此时，由于F有依赖顶点D，G有依赖顶点A，因此不对F和G进行处理。
第2步：将A,D依次加入到排序结果中。
第1步访问之后，A,D都是没有依赖顶点的，根据存储顺序，先访问A，然后访问D。访问之后，删除顶点A和顶点D的出边。
第3步：将E,F,G依次加入到排序结果中。
因此访问顺序是：B -> C -> A -> D -> E -> F -> G

include
include
include
include
define maxn 100001
typedef long long ll;
using namespace std;
int tupo[maxn];
struct A
{
```
 int next;
 int to;
```
}f[maxn];
int head[maxn];
int rudu[maxn];
int cnt;
void build(int u,int v)
{
```
 f[cnt].to=v;
 f[cnt].next=head[u];
 head[u]=cnt++;
```
}
int main()
{
```
 int n,m;
 while(~scanf("%d %d",&n,&m))
 {
     queue<int> q;
     memset(head,-1,sizeof(head));
     memset(rudu,0,sizeof(rudu));
     int s,e;
     cnt=1;
     for(int i=1;i<=m;i++)
     {
         scanf("%d %d",&s,&e);
         build(s,e);
         rudu[e]++;
     }
     for(int i=1;i<=n;i++)
         if(rudu[i]==0)
             q.push(i);
     int kk=0;
     while(!q.empty())
     {
         int fr=q.front();
         q.pop();
         tupo[kk++]=fr;
         for(int i=head[fr];i!=-1;i=f[i].next)
         {
             int to=f[i].to;
             rudu[to]--;
             if(rudu[to]==0)
                 q.push(to);
         }
     }
     for(int i=0;i<n;i++)
     {
         printf("%d\n",tupo[i]);
     }
 }
 return 0;
```
}

/
1 2
4 1
1 5
1 9
10 3
5 10
8 9
6 9
3 6
4 5 /