拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。 拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

如何求解有向图无环图的拓扑序列？

如何判断一个图是否有环？

848. 有向图的拓扑序列 - AcWing题库

1. 首先，将入度为0的点入队。
2. 然后，用宽搜遍历队列。
3. 将这个点出队，并加入拓扑数组中
4. 遍历这个点的所有出度
5. 将其出度点的入度数量减少一
6. 如果其出度点入度为0，入队

首先将（入度为0的点）入队，然后出队，依次遍历这个点的出边，删除出边。

删除后呈现这样：

再遍历出边是，如果连接点的入度减为0了，那就将这个点入队。

接着继续出队，遍历b，将b放入数组。

此时变成这样

接着将c入队，并遍历

结果：

接着将d入队，并出队。

最终结果：

#include<iostream>
#include<cstring>using namespace std;
const int N = 100009;
int h[N],e[N*2],ne[N*2],idx;
int q[N],in_degree[N],hh,tt=-1;
int n,m;
int toplist[N],k=1;//拓扑数组，存路径,k是存储的下标void add(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx;idx++;
}bool topsort(){for(int i=1;i<=n;i++){   //首先将入度为0的节点入队列if( !in_degree[i]){q[++tt] = i;}}while(hh<=tt){ //只要队列非空int t = q[hh++];//拿出一个入度为0的节点toplist[k++] = t;for(int i=h[t];i != -1;i=ne[i]){int j = e[i];in_degree[j]--;//不用担心变成负数，如果变成负数说明原来是0，如果是0的话就没有边指向这了。if( !in_degree[j]){q[++tt] = j;}}}return k==n+1;//最后一个入队的时候k也++了，所以要判断k是否等于n+1
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof(h));for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);add(a,b);in_degree[b]++;}bool tag = topsort();if(!tag){cout<<"-1";}else{for(int i=1;i<=n;i++){cout<<toplist[i]<<" ";}cout<<endl;}return 0;
}