#PQJ1929x10149. QOJ 1929_10149

    ID: 2756 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十六省联合省选2025拓扑排序二分图

QOJ 1929_10149

2025 联合省选 第一试图排列(graperm) 图排列(graperm) 【题目描述】 小Q 有m 个互不相同的正整数二元组{(ai, bi)}m i=1,其中对于所有1 ≤i ≤m,1 ≤ ai < bi ≤n。这m 个二元组满足如下.性.质:.不.存.在1 ≤i, j ≤n .满.足ai < aj < bi < bj。 小D 有一个1 ∼n 的排列p。小Q 和小D 利用他们手上的二元组和排列一起构建 了一张n 个点m 条边的无向图G = (V, E),其中V = {1, 2, . . . , n},E = {(pai, pbi) | i ∈{1, 2, . . . , m}}。 现在小I 得知了图G,他想要知道在小Q 的m 个二元组所具有的性质的前提下, 小D 手中的排列p 可能是什么。由于小I 手中的信息不足,排列p 有很多种可能,小I 希望你可以告诉他其中字典序最小的那一个。 小Q,小D 和小I 是很好的朋友,他们保证不会欺骗彼此,因此.存.在.至.少.一.个.排.列 p .满.足.条.件。 【输入格式】 从文件graperm.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行两个整数c, T,分别表示测试点编号和测试数 据组数,接下来输入每组测试数据。样例满足c = 0。 对于每组测试数据,第一行两个整数n, m,分别表示图G 的点数和边数,接下来 m 行,第i (1 ≤i ≤m) 行两个整数ui, vi,描述图G 的一条边。 【输出格式】 输出到文件graperm.out 中。 对于每组测试数据,输出一行一个1 ∼n 的排列p,表示题设条件下字典序最小的 排列。数据保证存在至少一个排列p 满足条件。 【样例1 输入】 1 0 2 2 4 2 3 1 3 4 4 2 5 4 5 6 2 3 7 4 2 8 3 1 第9 页 共12 页

2025 联合省选 第一试图排列(graperm) 9 1 4 10 3 4 【样例1 输出】 1 1 2 4 3 2 1 3 2 4 【样例1 解释】 该组样例共有2 组测试数据。 • 对于第一组测试数据, – 如果小D 的排列为[1, 2, 3, 4],那么小Q 拥有的二元组为{(1, 3), (2, 4)},但 取i = 1, j = 2 有1 < 2 < 3 < 4,因此不满足小Q 的二元组的性质。 – 如果小D 的排列为[1, 2, 4, 3],那么小Q 拥有的二元组为{(1, 4), (2, 3)},可 以证明其满足性质。 • 对于第二组测试数据,如果小D 的排列为[1, 3, 2, 4],那么小Q 拥有的二元组为 {(2, 3), (3, 4), (1, 2), (1, 4), (2, 4)},可以证明其满足性质。 【样例2】 见选手目录下的graperm/graperm2.in 与graperm/graperm2.ans。 该组样例满足测试点1, 2 的限制。 【样例3】 见选手目录下的graperm/graperm3.in 与graperm/graperm3.ans。 该组样例满足测试点3, 4 的限制。 【样例4】 见选手目录下的graperm/graperm4.in 与graperm/graperm4.ans。 该组样例满足测试点5, 6 的限制。 【样例5】 见选手目录下的graperm/graperm5.in 与graperm/graperm5.ans。 该组样例满足测试点7, 8 的限制。 第10 页 共12 页

2025 联合省选 第一试图排列(graperm) 【样例6】 见选手目录下的graperm/graperm6.in 与graperm/graperm6.ans。 该组样例满足测试点9 ∼11 的限制。 【样例7】 见选手目录下的graperm/graperm7.in 与graperm/graperm7.ans。 该组样例满足测试点12 的限制。 【样例8】 见选手目录下的graperm/graperm8.in 与graperm/graperm8.ans。 该组样例满足测试点13 ∼15 的限制。 【样例9】 见选手目录下的graperm/graperm9.in 与graperm/graperm9.ans。 该组样例满足测试点16 ∼18 的限制。 【样例10】 见选手目录下的graperm/graperm10.in 与graperm/graperm10.ans。 该组样例满足测试点19 ∼21 的限制。 【样例11】 见选手目录下的graperm/graperm11.in 与graperm/graperm11.ans。 该组样例满足测试点22 ∼25 的限制。 【子任务】 对于所有测试点, • 1 ≤T ≤10, • 2 ≤n ≤105,0 ≤m ≤2n, • ∀1 ≤i ≤m, 1 ≤ui, vi ≤n, ui̸ = vi,即G 没有自环, • ∀1 ≤i < j ≤m, {ui, vi}̸ = {uj, vj},即G 没有重边, • 保证存在至少一个排列p 满足条件。 第11 页 共12 页

2025 联合省选 第一试图排列(graperm) 测试点编号 n ≤ 特殊性质 1, 2 10 无 3, 4 2, 000 AC 5, 6 A 7, 8 C 9 ∼11 无 12 105 ABC 13 ∼15 AC 16 ∼18 A 19 ∼21 C 22 ∼25 无 特殊性质A:G 连通。 特殊性质B:G 中每个点的度数不超过2。 特殊性质C:G 中不存在简单环,即G 是一个森林。 第12 页 共12 页