linkkk
题意：
给出m组限制条件，要求构造一个长度为n的字典序最小的序列。每组a , b表示在序列里a在b前面。
思路：
建图：a − > b有向边，跑一个拓扑排序，将队列换为优先队列，表示每次将最小的弹出，就能保证字典序最小了。
代码：
// Problem: D - Restricted Permutation // Contest: AtCoder - AtCoder Beginner Contest 223 // URL: https://atcoder.jp/contests/abc223/tasks/abc223_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; const int maxn=2e5+100; int n,m,din[maxn]; vector<int>g[maxn],ans; priority_queue<int,vector<int>,greater<int> >q; int main() { cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); din[v]++; } for(int i=1;i<=n;i++) if(!din[i]){ q.push(i); } while(!q.empty()){ int t=q.top();q.pop(); ans.push_back(t); for(auto tt:g[t]){ if(--din[tt]==0) q.push(tt); } } bool flag=0; for(int i=1;i<=n;i++) if(din[i]>0) flag=1; if(flag){ puts("-1");return 0; } for(auto it:ans) cout<<it<<" "; return 0; }
