拓扑排序

什么是拓扑排序？

若一个由图中所有点构成的序列A没满足：对于图中的每条边(x,y)，x在A中都出现在y之前，则称A是该图中的一个拓扑排序。只适用于有向无环图（AOV网）。

入度

想要找到拓扑排序，我们要了解入度的概念：指有向图中某点作为图中边的终点的次数之和。

对于一个入度为零的点，即没有任何一个点指向该点，我们可以认为这个点在拓扑排序中处于顶点的位置。我们可以维护一个队列，将这些入度为零的点入队，此时这些点就已经有序，不需要再入队，即可将该点删除，即将它指向的下一个点的入度减一，然后再次寻找入度为零的点即可，这样，我们就构成了一个循环。

如何判断该图是否存在合法的拓扑序列呢？我们可以由定义得到，合法的拓扑序列，一定由图中所有点共同构成，因此只要队列中进入过n次元素，即可判断存在一个合法的序列。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,d[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 邻接表模板
// d 代表每个元素的入度
// top是拓扑排序的序列，cnt代表top中有多少个元素
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
bool topsort(){
    queue<int> q;
    int t;
    for(int i = 1;i <= n; ++i)// 将所有入度为0的点加入队列
        if(d[i] == 0) q.push(i);
    while(q.size()){
        t = q.front();//每次取出队列的首部
        top[cnt] = t;//加入到 拓扑序列中
        cnt ++; // 序列中的元素 ++
        q.pop();
        for(int i = h[t];i != -1; i = ne[i]){
            // 遍历 t 点的出边
            int j = e[i];
            d[j] --;// j 的入度 --
            if(d[j] == 0) q.push(j); //如果 j 入度为0，加入队列当中
        }
    }
    if(cnt < n) return 0;
    else return 1;

}
int main(){
    int a,b;
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        cin >> a >> b;
        add(a,b);
        d[b] ++;// a -> b , b的入度++
    }
    if(topsort() == 0) cout << "-1";
    else {
        for(int i = 1;i <= n; ++i){
            cout << top[i] <<" ";
        }
    }
    return 0;
}