前言
在看到“拓扑序列”这4个字的时候，笔者人是傻的。拓扑序列是啥？听着就感觉好厉害！然后，当我得知“拓扑”两个字其实是一个大家都知道的单词“Top”的音译时，我不禁在想：翻译成这样，估计是故意让大家觉得这个知识点很难的吧。事实证明的确是这样，拓扑排序的概念与实现都是非常简单的。别被看上去高大上的名字吓到了。
拓扑序列概念介绍
首先，我们给出一个如图的有向图
然后我们给出一个序列a={1，2，3，4}，我们随便在有向图中选择一条边，我们都能满足在序列a中，这条边起点的编号一定在终点的编号之前。那么，我们就称为序列a是这个有向图的拓扑序列。
根据拓扑序列的概念，我们能知道：对于某些有向图而言，它的拓扑序列是不唯一的。只要是一个序列满足拓扑序列的定义，我们就可以说这个序列是这张图的拓扑序列。
当然，并不是所有图都是存在拓扑序列的，如果我们发现有向图中存在环，那么无论如何我们也找不出一个序列满足拓扑序列的定义。
如图，我们发现如果在之前的图中加上一条边，那么这张图就没有拓扑序列了。
拓扑序列求法介绍
首先，我们需要复习（预习？）一下离散数学中的知识点，入度。
所谓入度，就是对于有向图中的一个点而言，有多少个箭头是指向它的的。比如在最上方的没有环的有向图中，点1的入度为0，点2与3的入度都为1，点3的入度为2。
在了解了入度后，我们开始进行拓扑排序，在排序中，我们使用的是BFS广度优先搜索的思路进行点的遍历。
0.初始化：建图，求出所有点的入度。
1.我们首先遍历全图要找到入度为0的点，我们在我们的图中首先找到了点1
广度遍历所有以1为起点的边，删除这些边，操作为点2的入度减去1，然后就是这样，我们把点1放进拓扑序列中的最前面，a={1}；
再次循环遍历所有还没有放进序列的点，我们发现图中点2的入度已经变成0了，标记出来重复对点1的操作，a={1，2}
继续遍历，我们找到了点3，操作。a={1，2，3}
最后找到了点4，所有点都操作完毕，a={1，2，3，4}，拓扑排序结束。
没有拓扑序列的有环图判断
之前我们说过，并不是所有的有向图都存在拓扑序列的，那么我们要怎么来进行判断呢？首先，我们放一个存在环的有向图来进行上述的算法
我们对于上述图按照之前的算法进行处理完点1，2后，会变成这样
此时，a={1，2}，按照算法，我们应该在剩下的点中寻找入度为0的点，然后我们发现，找不到了，由于有环的存在，我们已经无法在接下来的图中找到入度为0的点了，算法结束，最后序列a定格在a={1，2}无法继续更新。
如果根据上面的算法判断，程序会认为此时的a就是最后的拓扑序列，但是显然不是。我们发现a中的点的数量为2，小于点的总数5。所以，假如我们求出最后的序列中点的数量少于点的总数，那么我们就知道有向图中存在环，该图不存在拓扑序列。
拓扑排序的代码实现
例题链接：Acwing 有向图的拓扑序列
给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。输出格式共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。否则输出 −1。数据范围1≤n,m≤1e5输入样例：3 31 22 31 3输出样例：1 2 3
这道题就是一道板子题，所以我们直接贴上代码，不过要看懂代码你需要事先知道以下知识点
1.c++STL中 数据结构queue的基本使用方法
2.链式前向星的存图方法----->链式前向星CSDN博客
3.作者重定义的memset函数（ #define mem(a,b) memset(a,b,sizeof(a)) ）
//#pragma GCC optimize(2)#include<iostream>#include<iomanip>#include<cstdio>#include<string>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<map>#include<stack>#include<set>#include<bitset>#include<ctime>#include<cstring>#include<list>#define ll long long#define ull unsigned long long#define INF 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef pair<int, int> PII;const int N = 1e5 + 7;int n, m;int e[N], ne[N], h[N], id = 1; //链式前向星存图int rd[N]; //存放每个点的入度bool ch[N]; //用来判断该点有没有被放进序列中bool haveans = true; //用来判断是否有拓扑序列queue<int>q; //用来存放拓扑序列的队列void add(int a, int b) //加边的函数{e[id] = b;ne[id] = h[a];h[a] = id++;rd[b]++;}void topsort() //拓扑排序实现函数{bool flag = true; //flag为true就代表还能找到入度为0的点while (flag){flag = false; //先改为，找不到入度为0的点for (int i = 1; i <= n; i++){if (rd[i] == 0&&!ch[i]){ch[i] = true; flag = true; //找到了入度为0的点就把flag改为true，继续循环q.push(i); //把入度为0的点放进队列qfor (int j = h[i]; j != -1; j = ne[j]) //BFS遍历所有以i为起点的边{int k = e[j];rd[k]--; //每一条边的入度减一，删除该边}}}}}void solve(){bool flag = true;cin >> n >> m;mem(h, -1);for (int i = 0; i < m; i++){int a, b;cin >> a >> b;add(a, b);}topsort();if (q.size() != n) //如果队列中元素数量不等于点的总数就代表图中有环，没有拓扑序列cout << "-1" << endl;else //否则输出拓扑序列while (!q.empty()){cout << q.front();q.pop();if (!q.empty())cout << ' ';elsecout << endl;}}int main(){//std::ios::sync_with_stdio(false);//cin.tie(0), cout.tie(0);solve();return 0;}
作者：Avalon Demerzel，喜欢我的博客就点个赞吧，更多图论与数据结构知识点请见作者专栏《图论与数据结构》
