标题:想了一道关于拓扑排序的问题,自己试了很多次没有实现的办法,求思路
只看楼主
houruomu
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2014-7-26
 问题点数:0 回复次数:0 
想了一道关于拓扑排序的问题,自己试了很多次没有实现的办法,求思路
问题描述:
有一些输入的元素,我们暂且用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.
我试过两种方法:关系矩阵做排序索引+快速排序,或者拓扑排序(用有向图做深度优先搜索),但是这些方法都只能输出一种满足情况的解,而不能输出所有解,有什么其他的办法么?
搜索更多相关主题的帖子: 元素 
2014-08-13 18:40



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-434984-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.116446 second(s), 8 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved