Thám Hiểm Đồ Thị Theo Thứ Tự Từ Điển

Buổi 63 — Interactive & Constructive Graphs
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ đồ thị được cho trước).

Một nhà thám hiểm bắt đầu tại đỉnh $1$ của đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Ở mỗi bước, từ đỉnh hiện tại $u$, nhà thám hiểm hỏi người dẫn đường xem đỉnh kề chưa từng thăm có chỉ số nhỏ nhất của $u$ là đỉnh nào:

  • Nếu có đỉnh $v$ như vậy, nhà thám hiểm di chuyển sang $v$, đánh dấu $v$ đã thăm và đặt $u$ làm cha của $v$ (tốn 1 bước di chuyển).
  • Nếu không còn đỉnh kề nào chưa thăm, nhà thám hiểm quay lui về đỉnh cha của $u$ (tốn 1 bước di chuyển; nếu $u = 1$ thì kết thúc).

Hãy in ra tổng số bước di chuyển và thứ tự các đỉnh được thăm lần đầu.

Dữ liệu vào
  • Dòng đầu ghi hai số nguyên $N, M$ ($1 \le N \le 2000$, $0 \le M \le 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
  • Dòng đầu ghi tổng số bước di chuyển.
  • Dòng thứ hai ghi danh sách các đỉnh theo thứ tự được thăm lần đầu, cách nhau bởi dấu cách.
Ví dụ
Input Output
4 4
1 3
1 2
2 4
3 4
6
1 2 4 3
Giới hạn
  • $1 \le N \le 2000$
  • $0 \le M \le 10^5$
Draft saved