[ABC291E] Find Permutation（拓扑排序变种）

[ABC291E] Find Permutation

题面翻译

有一个 $1\sim N$ 的排列 $A_1,\cdots ,A_N$。
给定 $M$ 组关系 $(X_i,Y_i)$，每组关系表示 $A_{X_i}<A_{Y_i}$。
求出唯一一组合法的 $A$。如果答案不唯一，仅输出 No；否则输出 Yes 和求出的 $A$。

题目描述

$ 1,\ldots,N $ の並び替えである長さ $ N $ の数列 $ A=(A_1,\ldots,A_N) $ があります。

あなたは $ A $ を知りませんが、$ M $ 個の整数の組 $ (X_i,Y_i) $ について、$ A_{X_i}\ <\ A_{Y_i} $ が成り立つことを知っています。

$ A $ を一意に特定できるかどうか判定し、できるなら $ A $ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ X_1 $ $ Y_1 $ $ \vdots $ $ X_M $ $ Y_M $

输出格式

$ A $ を一意に特定できるとき、1行目に Yes と出力し、2行目に $ A_1,\ldots,A_N $ をこの順に空白区切りで出力せよ。

$ A $ を一意に特定できないとき、No とのみ出力せよ。

样例 #1

样例输入 #1

3 2
3 1
2 3

样例输出 #1

Yes
3 1 2

样例 #2

样例输入 #2

3 2
3 1
3 2

样例输出 #2

No

样例 #3

样例输入 #3

4 6
1 2
1 2
2 3
2 3
3 4
3 4

样例输出 #3

Yes
1 2 3 4

提示

制約

• $ 2\ \leq\ N\ \leq\ 2\times\ 10^5 $
• $ 1\ \leq\ M\ \leq\ 2\times\ 10^5 $
• $ 1\leq\ X_i,Y_i\ \leq\ N $
• 入力は全て整数である
• 入力に矛盾しない $ A $ が存在する

Sample Explanation 1

$ A=(3,1,2) $ であると一意に特定できます。

Sample Explanation 2

$ A $ として $ (2,3,1),(3,2,1) $ の $ 2 $ 通りが考えられます。

思路：看到题目中说的仅有一种方案的话，我们首先想到拓扑排序，一开始想到了差分约束，但是这里只有一种符号 <， 因此大概率可以用其他方法的，我们就想到了可以用拓扑排序，一番手玩后发现规律，从而写出代码即可

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e5 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e6 + 10;//一般求唯一合法的答案我们可以想到拓扑排序的
//拓扑排序怎么又忘了咋int a[N], d[N];
vector<int>ed[N];
int main()
{int n, m;cin >> n >> m;for(int i = 1; i <= m; i ++){int u, v;cin >> u >> v;ed[u].push_back(v);d[v] ++;		}queue<int>q;for(int i = 1; i <= n; i ++){if(!d[i]) q.push(i);}//应该是刚好遍历n次的int o = 1;while(!q.empty()){if(q.size() != 1) {cout << "No" << endl;return 0;}int k = q.front();q.pop();//一定要记得出队啊a[k] = o ++;for(auto it : ed[k]){d[it] --;if(d[it] == 0) q.push(it);}}cout << "Yes" << endl;for(int i = 1; i <= n; i ++){cout << a[i] << " ";}return 0;
}