Skip to content

11552: 【原1552】晓敏的全序集

题目

题目描述

author: yzh119 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1552

Description

晓敏定义了一个\(n\)个数上的全序,和\(q\)个关于这个全序的信息:i j代表\(i<j\)。

晓敏希望能得到一个可能的全序,如果有多个可能的全序,晓敏喜欢字典序(正常的字典序)最小的那个。

如果不存在可能的全序,那么输出第几个条件开始就出现了矛盾。

Input Format

第一行两个整数\(n\)和\(q\)。

第二行\(n\)个数代表这\(n\)个整数。

第三行到第\(q + 2\)行,每行两个整数i j代表\(i<j\)。

Output Format

共一行,一个整数\(k\),代表从第\(k\)个条件开始出现了矛盾,或者\(n\)个整数,代表这个全序下这\(n\)个整数从小到大排列的结果。

Sample Input

5 8
1 2 3 4 5
1 3
2 4
3 5
5 4
3 2
1 5
2 1
3 4

Sample Output

7

Sample Input

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

Sample Output

9 2 1 6

Limits

对于\(80\%\)的数据,这\(n\)个数为\(1,2,\cdots, n\)。

对于\(80\%\)的数据,不存在可能的全序。

对于\(100\%\)的数据,\(n\leq 10^5, q\leq 2 * 10^5\)。

对于\(30\%\)的数据,\(n\leq 5000, q\leq 5000\)。

所有的数均不超过int范围。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!