在拓扑排序的基础上加上了一个条件:尽可能按字典序排序,这就使得题目难度加大。
题解:拓扑排序+小根堆
拓扑排序是采用队列一个一个出队列来删除对应结点的边,那么我们只需要保证每次出队列的结点都尽可能小,就能保证字典序。
每次出队列的值都为队列中的最小值,刚好可以采用小根堆来实现。
code
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int head[N],Next[N],to[N],sum[N],cnt=1,a[N]; void build(int x,int y){ Next[cnt]=head[x]; to[cnt]=y; head[x]=cnt++; sum[y]++; } int main(){ priority_queue<int,vector<int>,greater<int>> que; int n,m,cnt2=0; cin>>n>>m; for (int i=1;i<=m;i++){ int x,y; cin>>x>>y; build(x,y); } for (int i=1;i<=n;i++) if (sum[i]==0) que.push(i); while (!que.empty()){ a[cnt2++]=que.top(); int fx=que.top(); que.pop(); for (int j=head[fx];j>0;j=Next[j]){ if (--sum[to[j]]==0) que.push(to[j]); } } for (int i=0;i<cnt2;i++) if (i==0) cout<<a[i]; else cout<<" "<<a[i]; return 0; }
标签:U107394,cnt,int,拓扑,Next,队列,排序,模板 From: https://www.cnblogs.com/purple123/p/18030388