| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 517 人关注过本帖
标题:想了一道关于拓扑排序的问题,自己试了很多次没有实现的办法,求思路
只看楼主 加入收藏
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
快速回复:想了一道关于拓扑排序的问题,自己试了很多次没有实现的办法,求思路
数据加载中...
 
   



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

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