1039 拓扑排序

╰半夏微凉° 2022-09-12 03:49 273阅读 0赞

Description

  1. 输入一张有向图, 输出拓扑排序后的的结果.

Input

  1. 输入第一行是一个int型整数t,表示有t组测试数据。接下来每组测试数据第一行为两个整数n,m(n<=300,0<=m<=n*(n-1)/2).表示后面有n个节点（编号为1，2，...，n ),m条有向边. 后面的m行中每行有两个int型整数X和Y，表示X号点到Y号点有一条有向边，表示Y号点必须出现在X号点之后.

Output

  1. 对于每组数据:若没有可行的拓扑方案,输出0.若可行方案存在，输出任意一个可行方案(n个节点编号,编号间使用一个空格隔开）每组数据的输出以一个回车结尾.

Sample Input

  1. 2
  2. 2 2
  3. 1 2
  4. 2 1
  5. 3 3
  6. 3 1
  7. 2 3
  8. 2 1

Sample Output

  1. 0
  2. 2 3 1

发表评论

表情：
评论列表 （有 0 条评论，273人围观）

还没有评论，来说两句吧...

相关阅读

    相关 拓扑排序

    拓扑排序是一张AOV网(Activity Of Vertex NetWork),并且是无环的网! 概念: 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列V1,V

    墨蓝墨蓝/ 0 赞/ 156 阅读

    相关 拓扑排序

    什么是拓扑排序? 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序

    冷不防冷不防/ 0 赞/ 354 阅读

    相关 拓扑排序

    拓 扑 排 序 一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就

    小鱼儿小鱼儿/ 0 赞/ 375 阅读

    相关 拓扑排序

    （1）有向无环图 无环的有向图，简称 DAG (Directed Acycline Graph) 图。 有向无环图在工程计划和管理方面的应用：除最简单的情况之外，几

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 414 阅读

    相关 拓扑排序

    拓扑排序： 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反

    淩亂°似流年淩亂°似流年/ 0 赞/ 481 阅读

    相关 拓扑排序

     一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程

    野性酷女野性酷女/ 0 赞/ 582 阅读