U715985

BX 的 Bug 依赖链 (BX's Bug Dependency Chain)

普及+/提高

题目背景

BX 同学最近迷上了全栈开发,并亲手搭建了一个炫酷的个人网站 CodeY。 然而网站刚一上线,就被热心的同学们(比如专抓漏洞的 JZ 和狂测试数据的 ZS)找出了漫天飞舞的 Bug。 BX 是一个非常听劝且行动力极强的人,别人只要指出一个 Bug,他就会立刻去修。

但随着修复工作的进行,BX 发现了网站架构中一个令人头疼的抽象设定:Bug 之间居然存在依赖关系! 比如,如果不先修复登录模块的 Bug,就根本无法复现并修复支付模块的 Bug。 由于 Bug 数量实在太多,网友们帮 BX 整理出了一份多达 MM 条的“Bug 依赖清单”。

题目描述

网站中总共有 NN 个已知 Bug,编号为 11 到 NN。 网友们提交了 MM 条依赖关系,每条依赖关系用一对整数 (u,v)(u, v) 表示,意味着必须先修复编号为 uu 的 Bug,才能去修复编号为 vv 的 Bug。

BX 是一个有强迫症的完美主义者。在所有“当前可以被修复的 Bug”中(即该 Bug 的所有前置 Bug 都已经被修复),他总是优先选择编号最小的 Bug 进行修复(编号越小说明暴露得越早,网友催得越急)。

请你编写程序,帮 BX 推导出一份完美的修 Bug 顺序表。 此外,由于网站代码可能是互相引用的“屎山”,依赖清单中可能会出现死锁(即循环依赖,比如修 A 需要先修 B,修 B 需要先修 C,修 C 又需要先修 A)。如果存在死锁导致 BX 无法修完所有的 Bug,请让他放弃挣扎,输出 WTF。

输入格式

第一行包含两个整数 N,MN, M,分别表示 Bug 的总数和依赖关系的总数。 接下来 MM 行,每行包含两个整数 u,vu, v,表示修复 Bug vv 的前置条件是修复 Bug uu。(输入可能包含重边,但保证不会有自己依赖自己的情况)。

输出格式

如果可以修完所有的 Bug,输出一行 NN 个用空格分隔的整数,表示 BX 修复 Bug 的完美顺序。 如果存在死锁(循环依赖)导致无法修完所有 Bug,只需输出一行字符串 WTF。

输入输出样例

输入样例 #1

text
5 4
1 2
3 2
3 4
5 1

输出样例 #1

text
3 4 5 1 2

输入样例 #2

text
3 3
1 2
2 3
3 1

输出样例 #2

text
WTF

说明/提示

【样例解释 1】

初始时,没有前置依赖的 Bug 是 3 和 5。BX 优先选择编号最小的 3 进行修复。 修完 3 后,4 的前置条件满足了,当前可修复的是 4 和 5。BX 选择 4。 修完 4 后,可修复的只有 5。BX 修 5。 修完 5 后,1 的前置条件满足了。BX 修 1。 修完 1 后,2 的前置条件全部满足(1 和 3 都修了)。BX 修 2。 最终顺序为:3 4 5 1 2。

【样例解释 2】

1 需要 3,3 需要 2,2 需要 1。陷入死锁循环,输出 WTF。

数据规模与约定

  • 对于 30%30\% 的数据,1≤N≤10001 \le N \le 1000,0≤M≤20000 \le M \le 2000。
  • 对于 100%100\% 的数据,1≤N≤1051 \le N \le 10^5,0≤M≤2×1050 \le M \le 2 \times 10^5,1≤u,v≤N,u≠v1 \le u, v \le N, u \neq v。

🚀 提交评测

登录并绑定洛谷账号后即可在此在线提交代码并实时评测。

前往登录

💡 题解 (0)

登录后即可撰写并分享您的解题思路。

暂无题解,快来发布全站第一篇题解吧!

💬 题目讨论 (0)

登录后可以发起或参与讨论。

暂无讨论内容。

📊 题目信息

题号U715985
难度普及+/提高
时间限制1000 ms
内存限制256 MB
题目来源洛谷题库
算法标签
贪心优先队列拓扑排序

⚡ 快速操作

在线提交代码在洛谷打开原题 ↗