Thám Hiểm Đồ Thị Theo Thứ Tự Từ Điển
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$
Community Discussion