拓扑排序

已关闭
dadingPython / C++入场费 3 金币0 次提交

题目描述

给定一个 DAG(有向无环图),输出它的所有可能的拓扑排序结果。每个拓扑序占一行,多个结果时按字典序排列各节点的编号。

输入格式

第一行两个整数 n m(1≤n≤15,1≤m≤100),分别表示节点数量和边的数量。节点编号为 1~n。接下来 m 行,每行两个整数 u v,表示一条从 u 指向 v 的有向边(1≤u,v≤n,u≠v)。保证输入构成 DAG。

输出格式

输出所有可能的拓扑排序结果。每个拓扑序占一行,节点编号之间用空格分隔。如果有多个结果,按字典序排列输出。

输入输出样例

样例 1

输入:

3 2
1 2
2 3

输出:

1 2 3

说明/提示

DFS + 逆序回溯,或者 Kahn 算法 + 排序。n≤15 时状态空间小,DFS 回溯可穷举所有拓扑序。