[拓扑排序 反向建图] 825E - Minimal Labels

[拓扑排序 编号字典序最小] 825E - Minimal Labels

题目

​​题目链接​​

思路

这题答案要求节点编号越小，打上的标签越小，即编号序列字典序最小，而非拓扑序列字典序最小。

想让当然地建图然后优先队列从小到大，这样每次编号小的先出去。

但这样不大对，看下面的例子，上面是正常建图，然后优先队列从小到大;下面是反向建图优先队列从大到小。

发现下面的方法更优

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<utility>
#include<set>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
#define endl '\n'
//CHECK MULTIPLY INPUT  !!!
//NEW DATA CLEAN  !!!
//THINK > CODE !!!
const int N=1e5+10;
vector<int>edge[N];
int deg[N],A[N],ans[N];
int n,m;
void topsort(){
  int cnt=0,flag=n;
  priority_queue<int,vector<int>,less<int> >q;//从大到小
  for(int i=1;i<=n;i++)
    if(deg[i]==0)q.push(i);
  while(!q.empty()){
    int t=q.top();
    q.pop();
    A[t]=flag--;
    for(auto to:edge[t]){
      deg[to]--;
      if(deg[to]==0)q.push(to);
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int v,u;cin>>u>>v;
    edge[v].push_back(u);
    deg[u]++;
  }
  topsort();
  for(int i=1;i<=n;i++)cout<<A[i]<<" ";
  return 0;
}