请编写程序,实现对有向无权图中的顶点进行拓扑排序的算法。
注意:如果拓扑序不唯一,输出任何一个序列都可以,由特殊裁判程序判定正确性。
输入格式:
输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。
随后一行顺序给出 n 个顶点对应的字符串,由不超过 3 个英文字母或数字组成。
接下来 m 行,每行给出一条有向边的起点编号、终点编号。顶点编号从 0 开始。同行数字和字符串均以一个空格分隔。
输出格式:
参考样例。
首先在一行中输出 该图拓扑序存在性为 x
,其中 x
为 1 表示该图顶点有拓扑序,为 0 表示没有。
随后在一行中按顶点拓扑序存输出每个顶点对应的字符串。为输出简单起见,每个字符串后有一个空格。
注意:如果拓扑序不存在,最后一行可以输出任何字符,均判为正确。
输入样例 1:
8 8
C0 C1 C2 C3 C4 C5 C6 C7
0 2
0 4
1 2
1 4
3 4
4 5
4 6
5 7
输出样例 1:
该图拓扑序存在性为 1
C0 C1 C3 C2 C4 C6 C5 C7
输入样例 2:
8 9
C0 C1 C2 C3 C4 C5 C6 C7
0 2
0 4
1 2
1 4
3 4
4 5
4 6
5 7
7 4
输出样例 2:
该图拓扑序存在性为 0
这里输出什么都不重要