C++

「拓扑排序」Topo_Sort 模版

生成拓扑序-模版

对于一个DAG,统计入度,入度先从入度为0的结点开始,将其入队,然后删去这个节点的所有出度,并维护整个区间的新的入度in_degree[],循环操作此过程,最后生成的ans[]即为生成的拓扑序。

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

int edge_num,node_num,map[105][105],in_degree[105],ans[105],tot;
queue<int>q;

void topo(){
    for(int i=1;i<=node_num;i++) ans[i]=0;
    tot=0;
    while(!q.empty()) q.pop();
    for(int i=1;i<=node_num;i++)
        if(in_degree[i]==0)
            q.push(i);
    while(!q.empty()){
        int u=q.front();
        ans[++tot]=u;
        q.pop();
        for(int i=1;i<=node_num;i++){
            if(map[u][i]){
                in_degree[i]--;
                if(in_degree[i]==0)
                    q.push(i);
            }
        }
    }
}

int main(){
    cin>>node_num>>edge_num;
    for(int i=1;i<=edge_num;i++){
        int x,y;
        cin>>x>>y;
        if(!map[x][y]){
            map[x][y]=1;
            in_degree[y]++;
        }
    }
    topo();
    for(int i=1;i<=tot;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}
分享到