[编程笔记]-Topo_Sort拓扑排序

概念

拓扑排序，就是对图中的点进行排序。

排序方式如下：

对于每一个点，它指向的点都排在它后面，指向它的点都排在它前面。

所以，图只能是有向图，还得是有向无环图。

实现

记录每一个点的入度，把入度为0的点加入队列，然后BFS一遍，每遍历一个点，就把它“删掉”，使其所有相邻点入度减一，然后再把入度为0的点加入队列。

无须用到vis数组的证明：如果重复遇到同一个点，则说明指向这个点的边不止一条，但是只有当入度为0时才会把这个点加入队列，所以这个点只会被遍历一次。

代码

由于这是个算法，所以模板不是很固定，所以就直接上模板题吧。

例题

AcWing848-有向图的拓扑排序

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n,m;
int x,y;
int dg[N];
vector<int> vec;

int idk;
int hd[N],to[N],ne[N];

void merge(int a,int b){
    to[++idk]=b;
    ne[idk]=hd[a];
    hd[a]=idk;
    dg[b]++;
}

bool topo(){
    int fns=0;
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(dg[i]==0)q.push(i);
    }
    while(!q.empty()){
        int now=q.front();q.pop();
        vec.push_back(now);
        fns++;
        for(int i=hd[now];i;i=ne[i]){
            dg[to[i]]--;
            if(dg[to[i]]==0)q.push(to[i]);
        }
    }
    return fns==n;
}

int main(){
    cin>>n>>m;
    while(m--){
        cin>>x>>y;
        merge(x,y);
    }
    if(topo()){
        for(int i=0;i<vec.size();i++)cout<<vec[i]<<" ";
    }
    else{
        cout<<-1;
    }
    return 0;
}

完结撒花o(￣︶￣)o