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

AT_agc013_b.[AGC013B] Hamiltonish Path

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 NN 个顶点和 MM 条边的连通简单无向图。顶点编号为 11 到 NN，边编号为 11 到 MM。第 ii 条边连接了顶点 AiA_i 和顶点 BiB_i。请找到并输出一个满足以下条件的路径：

  • 路径经过不少于 22 个顶点。
  • 路径不经过同一顶点超过一次。
  • 至少包含路径两端点之一的所有直接相连的顶点。

在本题给定的约束下，可以证明总是存在这样的路径。你可以输出所有可能解中的任意一个。

输入格式

输入通过标准输入给出，格式如下：

N M A1 B1 A2 B2 : AM BMN\ M\ A_1\ B_1\ A_2\ B_2\ :\ A_M\ B_M

输出格式

请输出一个满足条件的路径。

输出第 11 行包含路径中顶点的个数。

输出第 22 行以空格分隔的顺序输出路径中各顶点的编号，使它们形成一条路径。

输入输出样例

  • 输入#1

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

    输出#1

    4
2 3 1 4

  • 输入#2

    7 8
1 2
2 3
3 4
4 5
5 6
6 7
3 5
2 6

    输出#2

    7
1 2 3 4 5 6 7

  • 输入#3

    12 18
3 5
4 12
9 11
1 10
2 5
6 10
8 11
1 3
4 10
2 4
3 7
2 10
3 12
3 9
1 7
2 3
2 11
10 11

    输出#3

    8
12 4 2 5 3 9 11 8

说明/提示

限制条件

  • 2≤N≤1052\leq N \leq 10^5
  • 1≤M≤1051\leq M \leq 10^5
  • 1≤Ai<Bi≤N1\leq A_i < B_i \leq N
  • 所给的图是连通且简单的（任意两点之间最多只有一条直接连边）。

样例解释 1

与顶点 22 直接相连的顶点是 33 和 44。与顶点 44 直接相连的顶点是 11 和 22。所以，22 → 33 → 11 → 44 这条路径符合所有条件。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页