题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
拓扑排序

题目题干

拓扑排序

请编写程序,实现对有向无权图中的顶点进行拓扑排序的算法。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
注意:如果拓扑序不唯一,输出任何一个序列都可以,由特殊裁判程序判定正确性。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式:

输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后一行顺序给出 n 个顶点对应的字符串,由不超过 3 个英文字母或数字组成。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来 m 行,每行给出一条有向边的起点编号、终点编号。顶点编号从 0 开始。同行数字和字符串均以一个空格分隔。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式:

参考样例。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
首先在一行中输出 该图拓扑序存在性为 x,其中 x 为 1 表示该图顶点有拓扑序,为 0 表示没有。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后在一行中按顶点拓扑序存输出每个顶点对应的字符串。为输出简单起见,每个字符串后有一个空格。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
注意:如果拓扑序不存在,最后一行可以输出任何字符,均判为正确。OaY100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入样例 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
这里输出什么都不重要

答案解析

相关题目

求图中关键活动求图中关键活动请编写程序,实现求带权的有向图中关键活动的算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。 随后 m 行,每行
拓扑排序请编写程序,实现对有向无权图中的顶点进行拓扑排序的算法。 注意:如果拓扑序不唯一,输出任何一个序列都可以,由特殊裁判程序判定正确性。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求最小生成树的Prim算法请编写程序,实现在带权的无向图中求最小生成树的 Prim 算法。 注意:当多个待收录顶点到当前点集的距离等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两个正
求所有点对间最短路的Floyd-Warshall算法请编写程序,实现在带权有向图中求所有点对间最短路的 Floyd-Warshall 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求单源最短路的Bellman-Ford算法请编写程序,实现在带负值权的有向图中求单源最短路的 Bellman-Ford 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点
求单源最短路的Dijkstra算法请编写程序,实现在带权的有向图中求单源最短路的 Dijkstra 算法。 注意:当多个待收录顶点路径等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
双连通分量本题请你编写程序,输出给定无向连通图中的割点和割边。 输入格式: 输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤20)。 第二行给出两个正整数,依次为当前要创建的
欧拉回路本题请你编写程序,输出给定无向连通图中的欧拉回路。 输入格式: 输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤20)。 第二行给出两个正整数,依次为当前要创建的图的

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢