题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
图的连通性判断

题目题干

 图的连通性判断

请编写程序,用广度优先搜索输出给定无向图中的各个连通分量,并判断给定的无向图是否连通。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
注意输出顺序规定如下:2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

  • 每个连通分量的输出从其中编号最小的顶点开始;
  • 不同连通分量按其第一个顶点的编号增序输出,每个连通分量占一行;
  • 当一个顶点有多个邻接点时,按其输入的逆序进行访问,即最后输入的邻接点,在广度优先搜索中应被最先访问输出。

输入格式:

输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤10)。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第二行给出两个正整数,依次为当前要创建的图的顶点数 n 和边数 m(保证顶点数至少为 2 且不超过最大顶点数量)。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第三行给出 n 个英文字母,顺序对应每个顶点的信息。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后 m 行,每行给出一条无向边的两个端点的编号、以及边的权重。顶点编号从 0 开始,权重(≤230)为整数。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
同行数字、字符均以一个空格分隔。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式:

按照题面中规定的顺序,输出图中的连通分量每个顶点的信息。每个连通分量占一行,字符间不要有空格。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后,如果图不连通,则在一行中输出 有 x 个连通分量,其中 x 是连通分量的个数。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
最后一行输出 该图连通性为 y,其中图连通时 y 值为 1,否则为 0。2Ea100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入样例:

10
6 7
a b c d e f
2 0 2
2 3 1
3 0 3
3 4 4
2 4 2
4 0 5
4 5 1

输出样例:

aedcf
b
有 2 个连通分量
该图连通性为 0

答案解析

相关题目

验证六度空间理论所谓“六度空间理论”是指:在世界上任何两个陌生人之间所间隔的人数不会超过 6 个。本题就请你编写程序,根据输入的人与人之间的关系,统计以某个人为起点的所有满足该理论(即与该起点之间间隔
图的连通性判断请编写程序,用广度优先搜索输出给定无向图中的各个连通分量,并判断给定的无向图是否连通。 注意输出顺序规定如下: 每个连通分量的输出从其中编号最小的顶点开始; 不同连通分量按其第一个顶点
广度优先遍历请编写程序,用广度优先搜索输出给定无向图中的各个连通分量。 注意输出顺序规定如下: 每个连通分量的输出从其中编号最小的顶点开始; 不同连通分量按其第一个顶点的编号增序输出,每个连通分量占
深度优先遍历请编写程序,用深度优先搜索输出给定无向图中的各个连通分量。 注意输出顺序规定如下: 每个连通分量的输出从其中编号最小的顶点开始; 不同连通分量按其第一个顶点的编号增序输出,每个连通分量占
邻接表表示的图基本操作请编写程序,实现并测试邻接表表示的图的以下基本操作: 返回图中顶点的第一个邻接顶点 判断边是否存在 向图中插入边 从图中删除顶点及所有邻接于该顶点的边 输入格式: 输入首先在第
邻接矩阵表示的图基本操作 请编写程序,实现并测试邻接矩阵表示的图的以下基本操作: 获取图的顶点个数 判断边是否存在 找顶点的第一个邻接点 向图中插入边 从图中删除边 从图中删除顶点及所有邻接于该顶点
找众数 描述 输入多个实数,直到输入QUIT时停止,计算出众数。 输入 输入多个数,包含带有小数点的数,直到输入QUIT四个英文连续英文字母时停止。输完一个数即回车后输入下一个数。 输出 输出
检查单词大小写 描述 检查输入的一个句子中的单词大小写问题,约定检查规则如下: 句子中的第一个单词,首字母必须大写,剩余字母小写。 句子中其余的单词所有字母都是小写。 若有单词的首字母小写,中间
计算字母在字符串中的百分比 描述 给你一个字符串 s 和一个目标字符 letter ,返回在 s 中等于 letter 字符所占的 百分比 ,向下取整到最接近的百分比。 输入 第一行为字符串,第
求特殊自然数 描述 一个十进制自然数,它的七进制与九进制表示都是三位数,且七进制与九进制的三位数码表示顺序正好相反。编程求此自然数,并输出显示。 输入 无。 输出 三行: 第一行是此自然数的十进制表

提示声明

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

猜你喜欢