3474 - 求无向图的 BFS 序列

题目描述

现有 N 个顶点、 M 条边的无向图,请输出该无向图的 BFS 序列,优先遍历编号较小的顶点。

说明:从顶点 1 开始进行广度优先搜索(BFS),每次访问邻接点时按编号从小到大排序。

输入
  • 第 1 行:两个整数 N M ,表示顶点数和边数。
  • 接下来的 M 行:每行两个整数 U_i, V_i ,表示一条无向边 (U_i, V_i)
  • 顶点用 1, 2, \dots, N 编号。
输出

输出该无向图的 BFS 遍历序列(即从顶点 1 开始,按 BFS 顺序访问的所有顶点编号)。

样例

输入

4 5
1 2
1 4
3 4
1 3
2 4

输出

1 2 3 4
说明

提示

  • 数据范围: 1 \leq N, M \leq 100
  • 图中可能有重边,但无需重复处理。
  • 使用队列实现 BFS,并对每个节点的邻接点进行排序以保证优先访问编号小的顶点。
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 5
通过人数 4
金币数量 2 枚
难度 基础


上一题 下一题