#O1041. 拓扑排序

拓扑排序

题目描述

给定 nn 个点、mm 条有向边的有向图,求字典序最小的拓扑序。若图中存在环,输出 No。

题目类型

图的遍历、拓扑排序

输入格式

第一行两个整数 n,mn, m。

接下来 mm 行,每行两个整数 u,vu, v,表示一条 u→vu \to v 的边。

输出格式

一行:若可以拓扑排序,输出 nn 个整数(用空格分隔);否则输出 No。

样例 #1

样例输入 #1

4 4
1 2
1 3
2 4
3 4

样例输出 #1

1 2 3 4

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 点数
0≤m≤2×1050 \le m \le 2 \times 10^5 边数
  • 用入度为 0 的点入小根堆,保证字典序最小。