想了一道关于拓扑排序的问题,自己试了很多次没有实现的办法,求思路
问题描述:有一些输入的元素,我们暂且用1,2,3,4....表示,给出一些大小关系,如1>4, 6>8 等等,求出有多少种可能的排序满足这些关系,并且输出所有排序方法。
希望能有高效率的算法,暂且定为O(n log n)吧。
输入:
元素个数, 关系个数
关系1
关系2
....
输出:
排序方法个数
排序方法1
排序方法2
....
示例输入输出:
输入:
4 5
1 2
1 3
2 4
3 4
2 3
输出:
1
1 2 3 4
p.s.
我试过两种方法:关系矩阵做排序索引+快速排序,或者拓扑排序(用有向图做深度优先搜索),但是这些方法都只能输出一种满足情况的解,而不能输出所有解,有什么其他的办法么?