本系列所有题目均为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≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
算法原理
先来介绍拓扑序列就是边的起点要在终点前输出。
如图，A到B这条边，A是起点，B是终点，所以先输出A在输出B，B到D这条边，B是起点，D是终点，所以先输出B在输出D，这时候我们发现C还没有输出，且A到C这条边，起点A已经被输出过，所以我们可以删掉已经被输出过的点，当然也要删掉这个点所能走的边，这样就只剩下C到D的边，C是起点，D是终点，先输出C后输出D，最后只剩下D这个点作为起点时才输出它。因此顺序为A->B->C->D或A->C->B->D，你没看错，拓扑序列是可以存在多个的，但这道题只要求出其中一个即可，所以我们定义拓扑序列中先输出起点，在输出终点，需要注意的是如果存在一个自环的话，那么一定不会存在拓扑排序。
在上面分析的基础上，我们引入点的出度和入度。入度是指向该点的边的个数，出度是这个点指向其他结点的边的个数，这里用反证法进行证明：容易知道如果存在自环，即存在n点都至少具有一个出度和一个入度的话，那么从其中一个点沿着一条边走完所有的边就是n+1条边，由抽屉定理可知，其中一定会重复走过一个点，不仅表明了自环的存在，也说明这个终点在最开始被作为起点输出，这就不符合拓扑序列的定义，因此自环一定不存在拓扑序列，这个事实也告诉我们，拓扑序列先输出的一定是起点，也就是入度为0的点，并且拓扑序列的输出一定是n个而不是n+1个，然后从起点开始顺这它所连接的边不断往后走，输出一个点就删除上一个点到这个点的边，表示为让这个点的入度减一d[i]-1，也正由于队列只存储入度为0的点，并且只要使用过这个点作为起点遍历，那么这个点就再也不会入队，那么图中每个点一定只会在队列里出现过一次，我们可以额外用一个数组存储队列里存储过的点ans，并且其顺序就是拓扑序列的顺序。。
以上是拓序列的主要思想，它能够用来判断图中是否存在自环。那么我们可以用什么数据结构实现呢，对于图的遍历我们可以使用BFS，对于这道题我们只需要入度，我们可以使用d[N]来表示第i个点的入度，具体的使用方法可以看代码注释哦。
代码实现
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N = 100010;
queue<int> q;
int h[N],e[N],ne[N],idx;
int n,m;
int d[N];
void add(int a ,int b){
e[idx] = b,ne[idx] = h[a],h[a]=idx++;
}
void bfs(){
// 因为不是数组模拟队列，所以不会得到头指针和尾指针的移动状况，不能用这个来判断是否遍历了n个结点所以要用vector来存储结果
vector<int> ans; // 这就是存放答案的数组
// 找入度为0的点并入队
for(int i=1; i <= n; ++i){
if(!d[i]) q.push(i); // 将当前结点的编号放进去
}
// bfs进行拓扑序列
while(!q.empty()){ // 判断队列不为空
int t = q.front();
q.pop();
ans.push_back(t);
for(int i=h[t] ; i != -1; i = ne[i]){
int b = e[i];
d[b]--; // 先去边，在判断入度是否为0，因为到这个节点前就要把上一个上一个点到该点的一条边删掉，即入度-1
if(!d[b]){ // 是起点就加进队列，这是因为后面删除边会使一些点变成起点
q.push(b);
}
}
}
if(ans.size() == n) // 如果不存在自环,n个点都可以作为起点
{
for(int i=0;i < ans.size() ; ++i){
cout << ans[i] << ' ';
}
cout << endl;
}
else{ // 否则存在自环，不存在拓扑序列
cout << "-1" << endl;
}
}
int main(void){
cin >> n >> m;
memset(h,-1,sizeof h);
for(int i=0; i < m ; ++i){
int a,b;
cin >> a >> b;
add(a,b); // a连接b
d[b]++; // b的入度+1
}
bfs();
return 0;
}
原文地址：http://www.cnblogs.com/WangChe/p/16924924.html
