vijos拓扑编号（逆向拓扑排序+优先队列）

题目地址：https://vijos.org/p/1790

描述

H国有n个城市，城市与城市之间有m条单向道路，满足任何城市不能通过某条路径回到自己。

现在国王想给城市重新编号，令第i个城市的新的编号为a[i]，满足所有城市的新的编号都互不相同，并且编号为[1,n]之间的整数。国王认为一个编号方案是优美的当且仅当对于任意的两个城市i,j，如果i能够到达j，那么a[i]应当<a[j]。

优美的编号方案有很多种，国王希望使1号城市的编号尽可能小，在此前提下，使得2号城市的编号尽可能小...依此类推

输入

第一行读入n,m，表示n个城市，m条有向路径。

接下来读入m行，每行两个整数:x,y
表示第x个城市到第y个城市有一条有向路径。

输出

输出一行:n个整数
第i个整数表示第i个城市的新编号a[i]，输出应保证是一个关于1到n的排列。

解决：逆向拓扑排序+贪心就可以了

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2e5+10;
struct st{
    int from,to,next;
}edge[M];
int head[N],cnt,n,m;
int r[N]={0};
int a[N];
void addedge(int u,int v){
    cnt++;
    edge[cnt].from=u;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void bfs(){
    priority_queue<int,vector<int>,less<int> >q;
    for(int i=1;i<=n;i++){
        if(r[i]==0) q.push(i);
    }
    int ans=n;
    while(!q.empty()){
        int st=q.top();q.pop();
        a[st]=ans;ans--;
        for(int i=head[st];i!=0;i=edge[i].next){
            r[edge[i].to]--;
            if(r[edge[i].to]==0){
                q.push(edge[i].to);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        addedge(v,u);
        r[u]++;
    }
    bfs();
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
} 

写于2020/8/19 21:20