当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5195:DZY Loves Topological Sorting

题目描述
A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $(u\rightarrow v)$ from vertex $u$ to vertex $v$, $u$ comes before $v$ in the ordering.
Now, DZY has a directed acyclic graph(DAG). You should find the lexicographically largest topological ordering after erasing at most $k$ edges from the graph.
输入解释
The input consists several test cases. ($TestCase\leq 5$)
The first line, three integers $n,m,k(1\leq n,m\leq 10^5, 0\leq k\leq m)$.
Each of the next $m$ lines has two integers: $u,v(u\not= v, 1\leq u,v\leq n)$, representing a direct edge$(u\rightarrow v)$.
输出解释
For each test case, output the lexicographically largest topological ordering.
输入样例
5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3
输出样例
5 3 1 2 4
1 3 2

提示
Case 1.
Erase the edge (2->3),(4->5).
And the lexicographically largest topological ordering is (5,3,1,2,4).
来自杭电HDUOJ的附加信息
Recommend hujie

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #35

源链接: HDU-5195

最后修改于 2020-10-25T23:20:36+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/2000MS(Java/Others) 131072/131072K(Java/Others)