OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题1225--拓扑排序

1225: 拓扑排序

时间限制: 1 Sec  内存限制: 128 MB
提交: 52  解决: 18
[提交] [状态] [讨论版] [命题人:]

题目描述

众所周知三相之力是均衡教派的镇派之宝,代表着均衡教派的教义。历来掌握在每一代教主手中,但是影流之主的叛变,使得这件神器落入他手。现在你需要合成这件装备,如下图所示三相之力由狂热,耀光,净蚀合成,而狂热又是由两把短剑合成,耀光由蓝水晶合成,净蚀由红水晶和长剑合成,每个合格的召唤师都熟知出装过程,当然这题不是教你怎么出装的,请你完成下面的题目(或许与出装类似)。 





本题:给出一个有向无环的连通图,对其进行拓扑排序,并输出拓扑序列,可能序列不唯一,请你输出字典序最小的序列。 





例如此图的拓扑排序序列有:

2 3 1 4 5 6 7

3 2 1 4 5 6 7

2 3 4 1 5 6 7

3 2 4 1 5 6 7

2 3 1 4 6 5 7

3 2 1 4 6 5 7

2 3 4 1 6 5 7

3 2 4 1 6 5 7 
...... 
显然拓扑序列很多,但是对于此题你需要输出字典序最小的序列, 
所以答案为2 3 1 4 5 6 7  

输入

第一行先是一个正整数n (n ≤ 500)代表图中顶点数,紧接着是一个空格以及正整数m(m ≤ 10000)代表边数,接下来m行每一行两个正整数u,v用空格隔开代表u到v有一条有向边,(u, v ≤ n),输入保证没有重边以及自环,上图为样例解释。 

输出

一行共n个数,每两个数之间有一个空格,表示该有向无环图的字典序最小的拓扑序列。 

样例输入 Copy

7 6
2 1
3 1
3 4
1 5
1 6
6 7

样例输出 Copy

2 3 1 4 5 6 7

提示

在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序。对于数字1、2、3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后。按照这样的规定,5个数字的所有的排列中最前面的是12345,最后面的是 54321。  
--来源百度百科 关键字  "字典序 

来源/分类

图论