工序先后表

普及+/提高 GESP GESP7级 每日一题 Day7 拓扑排序

题目描述

题目描述

一个工程有 n 道工序,部分工序之间有先后要求。要求 a 在 b 之前完成记为 a 指向 b。请输出一种满足所有要求的工序顺序;如果不存在这样的顺序,输出 -1。若有多种顺序,请输出字典序最小的一种。

输入格式

第一行两个整数 n 和 m。
接下来 m 行,每行两个整数 a 和 b,表示工序 a 必须在工序 b 之前完成。

输出格式

若存在合法顺序,输出 n 个整数;否则输出 -1。

数据范围

1 <= n <= 200000
0 <= m <= 300000
1 <= a,b <= n

输入格式

第一行两个整数 n 和 m。
接下来 m 行,每行两个整数 a 和 b,表示工序 a 必须在工序 b 之前完成。

输出格式

若存在合法顺序,输出 n 个整数;否则输出 -1。

数据范围

1 <= n <= 200000
0 <= m <= 300000
1 <= a,b <= n

样例输入 1

5 4
1 3
2 3
3 4
2 5

样例输出 1

1 2 3 4 5
时间限制: 1000ms
内存限制: 256MB
通过率: 0.0%
提交数: 0

设置

导航栏小工具

时钟
显示实时时钟(默认组件)
📝
代码粘贴板
快速创建和分享代码片段