我们首先来看看百度百科对拓扑序列的解释
拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。 拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
百度百科给的求的过程，我们一起来了解一下
对于一个给定的有向图，得到其拓扑序列的步骤如下：
①从图中选择一个入度为0的顶点，并输出该顶点；
②从图中删除该顶点及其相关联的有向边，调整被删除有向边的终点的入度（入度减1）；
③重复①和②；
④直到所有顶点均被输出，拓扑序列完成；否则，无拓扑序列。
可以证明，任何一个无环的有向图一定有拓扑序列，有环的有向图则无拓扑序列。
相信大家看了度娘的解释一定清楚了吧，那么我们接下来就把acwing上的一道题拿来练练手！
我们先看下题目描述：(这道题可以在acwing 上搜索 有向图的拓扑序列 来查看额原题额，顺便也把链接放这吧，就是不知道进不进得去，进不去就自己去acwing 上搜索。有向图的拓扑序列)
本着下面这个原则，最终成功拿下了！
while(有bug){ 改bug if（accept）break; }
成功拿下的Code
#include<bits/stdc++.h> using namespace std; int n, m; const int N = 1000010; int h[N], ne[N], e[N], idx; int d[N];//d数组表示某点的入度 void add(int a,int b){//存储图，以邻接表的方式 e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int q[N];//定义个队列（数组模拟队列），装入度为0的点。 （这也可以不用队列，就看做是个普通的数组也行） int topSe(){ int hh = 0, tt = 0;//初始化队头和队尾 for (int i = 1; i <= n;i++){ if(!d[i]) q[tt++] = i; //把入度为0的点入队 } while(hh<=tt){//队列不空就执行下面的 int t = q[hh++];//取出队头的数，然后将对头的数出队。(这就是数组模拟队列的优点吧) for (int i = h[t]; i != -1;i=ne[i]){//遍历头结点的出边 int j = e[i];//获取到达的点 d[j]--;//将出边能到达的点，把入度减1（就是把边删掉） if(d[j]==0){//如果结点的入度为0 d[j] = d[t] + 1;//距离 在上一个点的距离基础上 +1 q[tt++] = j;//将这个入度为0的点加入队列 } } } return tt == n;//队列长度等于n，返回1，否则返回0 } int main(){ memset(h, -1, sizeof(h));//将h数组全部置为-1，（这个看自己的写法，和上面得第20行有关） cin >> n >> m; for (int i = 0; i < m;i++){ int a, b; cin >> a >> b; add(a, b); d[b]++;//因为是 a -> b ，所以，b 的入度要加 1 } if(topSe()){//如果存在拓扑序列，则输出 for (int i = 0; i <n;i++)//我们可以发现，队列中的入队顺序就是拓扑序列 cout << q[i] << " "; cout << "\n"; }else //不存在则输出-1 cout << "-1\n"; return 0; }
贴心时刻
担心各位老板难以滑动代码，我还特地的准备了图片版！
