【vijos1790】拓扑编号

            

problem

solution

codes

//vijos1790
//拓扑排序的本质是本次将入度为0的点排到序列的最前端。
#include
#include
#include
#define maxn 100000+10
using namespace std;
int n, m, in[maxn], ans[maxn];
vector<int>G[maxn];
priority_queue<int>q;//默认小根堆
int main(){
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int a, b;  cin>>a>>b;
        G[b].push_back(a); //反向求拓扑序
        in[a]++;
    }
    for(int i = 1; i <= n; i++)//初始化,入度为0在最前
        if(in[i]==0)q.push(i);
    int num = n;  //反向给节点编号
    while(!q.empty()){
        int t = q.top();  q.pop(); //每次取出编号最小的城市操作
        ans[t] = num--;
        for(int i = 0; i < G[t].size(); i++)
            if(--in[G[t][i]]==0)q.push(G[t][i]);
    }
    for(int i = 1; i <= n; i++)cout<" ";
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像