拓扑排序
已关闭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 回溯可穷举所有拓扑序。