题目详情题解（0）讨论（0）提交记录（0）

A30869.【算法】Gold King浅涉拓扑

入门

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

拓扑是研究几何图形或空间在连续改变形状后还能保持不变的一些性质的一个学科。Gold King的涉猎范围广泛，兜兜转转一圈后，还是踏入了拓扑大门，但是一入大门深似海，从此回头不由人。

    拓扑大门里外围级的研究，Gold King选择了拓扑排序进行了深入，这是检测图中是否存在环的一个好方法。拓扑排序是对有向无圈图顶点的一种排序，它使得如果存在一条从顶点  vi  到顶点  vj  的有向路径，那么在排序中  vj  处于  vi  后面。

算法思想是：先找出任意一个没有入边的顶点。然后显示

输入格式

第一行输入两个整数n和m，表示有n个顶点和m条边。 接下来输入m行，每行两个整数 vi 和 vj ，表示从顶点 vi 到顶点 vj 有一条有向边。

输出格式

输出拓扑排序结果，如果图中存在环，则输出“has circle.”。
我们拓扑排序结果不唯一，本题采用栈的方式来存储满足没有入边顶点的数据。

输入输出样例

  • 输入#1

    样例1输入：
4 4
1 2
1 3
4 3
2 4
样例2输入：
3 3
1 2
2 3
3 1
样例3输入：
7 12
1 2
4 3
1 4
2 5
2 4
3 6
4 6
1 3
4 7
5 4
5 7
7 6

    输出#1

    样例1输出：
1 2 4 3
样例2输出：
has circle.
样例3输出：
1 2 5 4 3 7 6

说明/提示

2 <=n <=m <=30

首页