题意描述:
给定字母表的前n个大些字母,以及这些字母间两两之间的大小关系(这样的关系给定m组),问由这m组关系能否确定n个字母的整体顺序,如果能输出按续排列的字母。
显然,本题就是拓扑排序,不过题目的要求使得我们要处理一些细节。
下面我先说以下拓扑排序:
严蔚敏《数据结构》上的定义是:由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序
直观的说偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间均可比较。
举个例子,一个大的工程通常有许多小的工程组成,这些小工程之间通常存在某些先后顺序;当然有些小工程之间不存在先后关系,它们是可以并行的。如果两个小工程直接或间接的相互依赖,就是两个小工程互为对方的先行条件,整个工程将无法进行下去。用一个个顶点分别表示这些小工程,用有向的边表示小工程之间的依赖关系,我们可以得到一个有向图。
拓扑排序可以帮助我们确定这些小工程开始的顺序,并且能够判定小工程之间是否存在相互依赖(图中是否有回路)。
拓扑排序的具体做法是:
1.在有向图中选择一个没有前驱(入度为0)的顶点,输出
2.从图中删除该顶点和所有以它为尾的弧,并更新相关点的入度
3.重复1,2步,直到所有顶点都被输出,或者发现图中存在回路。
如果结合上面所举的工程的例子,没有依赖(先后)关系的工程是可以并行的,但是就本题(zoj1060)而言,它要求每两个点之间的关系都是确定的,是不允许出现并行的,所以,当某一时刻,我们发现入度为0的点不止1个时,排序就失败了。
本题的输出分为三种情况,并且要求输出所用的条件个数,因此每增加一个条件就要做一次拓扑排序。
以下是本题代码,第一次写,有点乱,将就一下把~~
测试数据:http://poj.org/showmessage?message_id=133905

posted on 2012-08-16 19:19 小鼠标 阅读(1795) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年8月>
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜