计算拓扑序列的一个方式是，用BFS来尝试访问所有的节点，但是有一个约束就是只有入度为 0 0 0的节点才能被加入到扩展队列里。每次从队列里取出一个节点，也就同时在图中将这个节点拆除，所以它的所有后继的节点都减少 1 1 1，如果已经减少到 0 0 0，那么就可以加入到队列中。
在上面的例子中，一开始只有
a
a
a的入度是
0
0
0，所以先把
a
a
a加入到队列中，队列中：
a
a
a
然后取出队头
a
a
a并在图中拆除，然后它的后继
c
c
c的入度变成
1
1
1，
b
b
b的入度变成
0
0
0，把
b
b
b加入到队列里，队列中：
b
b
b
然后取出队头
b
b
b并在图中拆除，然后它的后继
c
c
c和
d
d
d的入度都变成
0
0
0，都加入到队列里，队列中是：
c
d
c~d
c d
或者
d
c
d~c
d c
接下来也是重复这个过程，最后得到拓扑序列是 a b c d a~b~c~d a b c d或者 a b d c a~b~d~c a b d c（取决于 c c c和 d d d哪个先从“ d d d的所有后继”这个集合中访问）。
在实现拓扑排序时，用模拟队列来代替STL的队列比较方便。一方面是，观察上面的过程可以发现，只要所有节点都被加入到队列里了，那么就能说明所有的节点都能被访问，就说明存在拓扑序列。如果用模拟队列，由于它的两个指针一直往后移的特性，只要看一下队尾指针tt是不是在n-1位置就能知道是不是这n个元素都加入过队列中了。
另外，由于模拟队列删除元素只是做++hh的操作，而没有破坏队头hh位置的元素取值，所以最后输出拓扑序列的时候可以直接从0到n-1遍历一下队列，输出的就是拓扑序了。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
// 记录每个节点的入度
int d[N];
// 邻接表
int h[N], e[N], ne[N], idx;
// 邻接表添加有向边
void add_edge(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
// 模拟队列
int q[N], hh, tt = -1;
// 拓扑排序，如果存在拓扑序返回真
bool topo_sort() {
// 先将所有入度为0的节点入队
for (int i = 1; i <= n; i ++ ) {
if (!d[i])
q[ ++ tt] = i;
}
// BFS访问过程
while (hh <= tt) {
// 取队头节点t
int t = q[hh ++ ];
// 删除节点t，所以将节点t的所有后继j的入度-1
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
d[j] -- ;
// 如果已经减少到0了，就加到队列里
if (!d[j]) q[ ++ tt] = j;
}
}
// 如果所有n个节点都加入过队列，就存在拓扑序
return tt == n - 1;
}
int main() {
// 初始化邻接表
memset(h, -1, sizeof h);
// 读取m条有向边，同时维护节点的入度
cin >> n >> m;
for (int i = 0; i < m; i ++ ) {
int a, b;
cin >> a >> b;
add_edge(a, b);
d[b] ++ ;
}
// 如果存在拓扑序，模拟队列中依次入队的顺序就是拓扑序
if (topo_sort()) {
for (int i = 0; i < n; i ++ )
cout << q[i] << ' ';
cout << endl;
}
else {
cout << -1 << endl;
}
return 0;
}