题目详情题解（0）讨论（0）提交记录（0）

AT_abc291_e.[ABC291E] Find Permutation

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个长度为 NN 的数列 A=(A1,…,AN)A=(A_1,\ldots,A_N)，它是 1,…,N1,\ldots,N 的一个排列。

你并不知道 AA 的具体内容，但你知道 MM 个整数对 (Xi,Yi)(X_i,Y_i)，满足 AXi<AYiA_{X_i} < A_{Y_i}。

请判断是否能够唯一确定数列 AA，如果可以，请输出 AA。

输入格式

输入通过标准输入按以下格式给出。

NN MM
X1X_1 Y1Y_1
⋮\vdots
XMX_M YMY_M

输出格式

如果能够唯一确定 AA，第一行输出 Yes，第二行按顺序输出 A1,…,ANA_1,\ldots,A_N，用空格分隔。

如果不能唯一确定 AA，仅输出 No。

输入输出样例

  • 输入#1

    3 2
3 1
2 3

    输出#1

    Yes
3 1 2

  • 输入#2

    3 2
3 1
3 2

    输出#2

    No

  • 输入#3

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

    输出#3

    Yes
1 2 3 4

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Xi,Yi≤N1 \leq X_i, Y_i \leq N
  • 所有输入均为整数
  • 保证存在至少一个不矛盾的 AA

样例解释 1

可以唯一确定 A=(3,1,2)A=(3,1,2)。

样例解释 2

AA 可能为 (2,3,1)(2,3,1) 或 (3,2,1)(3,2,1)，有两种可能。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页