传送门

题意

有一个长度为 $N$ 的排列 $A_1 \dots A_N$，然后给出 $M$ 对大小关系：输入 $i,j$ 表示 $A_i<A_j$。问 $A$ 是否只有一种可能，若是，输出Yes然后输出 $A$，如果不是输出No。

题解

如果要 $A$ 只要一种可能，则必须要求每两个数的大小关系都确定，因此我们对每一对输入的 $(i,j)$ 建边 $i->j$，然后跑拓扑排序，如果有环（大小关系矛盾）或者队列里同时有两个数（这两个数可以调换位置）则输出No，否则按照拓扑排序的序列得出答案。

#include <map>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 200010;
int n, m, tot, tp[maxn], rd[maxn], a[maxn];
map <pair<int, int>, bool> p;
queue <int> q;
vector <int> g[maxn];
int main () {
  ios::sync_with_stdio (false), cin.tie (0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if (p.find({x, y}) != p.end ()) continue;
    g.push_back (y);
    rd[y]++;
    p[{x, y}] = true;
  }
  for (int i = 1; i <= n; i++) {
    if (!rd[i]) q.push (i);
  }
  while (!q.empty ()) {
    if (q.size () > 1) {
      cout << "No";
      return 0;
    }
    int x = q.front ();
    q.pop ();
    tp[++tot] = x;
    for (int y : g) {
      rd[y]--;
      if (!rd[y]) q.push(y);
    }
  }
  if (tot != n) {
    cout << "No";
    return 0;
  }
  for (int i = 1; i <= n; i++) a[tp[i]] = i;
  cout << "Yes\n";
  for (int i = 1; i <= n; i++) cout << a[i] << ' ';
  return 0;
}