首页 > 试题广场 >

带权的DAG节点排序

[编程题]带权的DAG节点排序
  • 热度指数：535 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

DAG即Directed Acyclic Graph,有向无环图.用DAG可以描述一些有依赖关系的任务组,而这些任务还有另外一个属性,即都有一个权重,标示这个任务的重要性.

我们需要你来实现一个算法,对DAG里面的节点进行排序,保证排序不违背DAG的依赖关系,即一个任务A如果排在任务B前面,那么在DAG中不能存在由B到A的路径.另外一个要求就是,让权重大的任务尽量优先执行.


输入描述:
在第一行给定DAG的节点数n和边数e.

后面n行,每一行是 节点的 标号和权重, seq weight.

最后e行,每一行是对于边的描述, s t.


输出描述:
排序好的节点标号,在一行内输出,空格隔开.
示例1

输入

4 4
1 2
2 3
3 5
4 4
1 2
1 3
2 4
3 4

输出

1 3 2 4
算法知识视频讲解
开通博客

暂无题解

问题信息

图 dfs
上传者：小小
难度：
6条回答 3568浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号