[ABC291E] Find Permutation 题解

· · 题解

本题需要使用拓扑排序。

因为题目中保证有解，所以将题目中的大小关系作为有向边建图，可得该图为一 DAG（有向无环图）。

根据拓扑序的性质：对于有向无环图 G=(V,E) 中任意一对顶点 u 和 v，若边 <u,v>\in E，则 u 在拓扑序中出现在 v 之前；就可以构造出需要的排列。

那么如何判断多解呢？显然，如果有多个合法的拓扑序，就会有多解。所以，如果 BFS 过程中队列里有多个元素，那么拓扑序就不唯一（可以通过任意的顺序遍历队列中的元素），直接判断输出即可。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> g[200001],a;
int d[200001],b[200001];
map<pair<int,int>,bool> mp;
main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v; cin>>u>>v;
    if(mp[make_pair(u,v)])continue;
    mp[make_pair(u,v)]=true;
    d[v]++,g[u].emplace_back(v); // 建图
  }
  queue<int> s;
  for(int i=1;i<=n;i++)if(!d[i])s.emplace(i);
  while(!s.empty()){
    if(s.size()>1){cout<<"No\n"; return 0;} // 有多解
    int t=s.front(); s.pop(); a.emplace_back(t);
    for(int i:g[t])if(!--d[i])s.emplace(i);
  }
  cout<<"Yes\n";
  for(int i=0;i<n;i++)b[a[i]]=i+1; // 根据顺序确定排列
  for(int i=1;i<=n;i++)cout<<b[i]<<' ';
  cout<<endl;
  return 0;
}