102914: [Atcoder]ABC291 E - Find Permutation
Description
Score : $500$ points
Problem Statement
There is a length-$N$ sequence $A=(A_1,\ldots,A_N)$ that is a permutation of $1,\ldots,N$.
While you do not know $A$, you know that $A_{X_i}<A_{Y_i}$ for $M$ pairs of integers $(X_i,Y_i)$.
Can $A$ be uniquely determined? If it is possible, find $A$.
Constraints
- $2 \leq N \leq 2\times 10^5$
- $1 \leq M \leq 2\times 10^5$
- $1\leq X_i,Y_i \leq N$
- All values in the input are integers.
- There is an $A$ consistent with the input.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$
Output
If $A$ can be uniquely determined, print Yes in the first line. Then, print $A_1,\ldots,A_N$ in the second line, separated by spaces.
If $A$ cannot be uniquely determined, just print No.
Sample Input 1
3 2 3 1 2 3
Sample Output 1
Yes 3 1 2
We can uniquely determine that $A=(3,1,2)$.
Sample Input 2
3 2 3 1 3 2
Sample Output 2
No
Two sequences $(2,3,1)$ and $(3,2,1)$ can be $A$.
Sample Input 3
4 6 1 2 1 2 2 3 2 3 3 4 3 4
Sample Output 3
Yes 1 2 3 4
Input
题意翻译
有一个 $1\sim N$ 的排列 $A_1,\cdots,A_N$。 给定 $M$ 组关系 $(X_i,Y_i)$，每组关系表示 $A_{X_i}<A_{Y_i}$。 求出唯一一组合法的 $A$。如果答案不唯一，仅输出 `No`；否则输出 `Yes` 和求出的 $A$。Output
分数：500分
问题描述
有一个长度为 N 的序列 A=(A_1,\ldots,A_N)，它是 1,\ldots,N 的一个排列。
虽然你不知道 A，但你知道对于 M 对整数对 (X_i,Y_i)，有 A_{X_i}<A_{Y_i}。
可以唯一确定 A 吗？如果可能，请找出 A。
约束
- 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。
输入
输入从 Standard Input 以以下格式给出：
$N$ $M$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$
输出
如果可以唯一确定 A，则在第一行打印 Yes。然后在第二行打印 A_1,\ldots,A_N，用空格分隔。
如果无法唯一确定 A，只需打印 No。
样例输入 1
3 2 3 1 2 3
样例输出 1
Yes 3 1 2
我们可以唯一确定 A=(3,1,2)。
样例输入 2
3 2 3 1 3 2
样例输出 2
No
两个序列 (2,3,1) 和 (3,2,1) 可以是 A。
样例输入 3
4 6 1 2 1 2 2 3 2 3 3 4 3 4
样例输出 3
Yes 1 2 3 4