trang chủ / đề bài / roundtrip

Vòng Tròn

Đề bài

Mô tả

Có n thành phố và m con đường hai chiều. Hãy tìm một vòng tròn — hành trình bắt đầu từ một thành phố, đi qua ít nhất hai thành phố khác, và quay trở lại điểm xuất phát — trong đó tất cả các thành phố trung gian phải khác nhau.

Dữ liệu vào

  • Dòng 1: hai số nguyên n và m.
  • m dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b — một con đường.

Dữ liệu ra

  • Nếu tồn tại vòng tròn: in số lượng thành phố k trên hành trình (thành phố đầu tiên xuất hiện hai lần), rồi in danh sách các thành phố.
  • Nếu không tồn tại: in IMPOSSIBLE.

Ràng buộc

  • 1≤n≤105
  • 1≤m≤2×105

Ví dụ

Input Output Giải thích
5 6
1 3
1 2
5 3
1 5
2 4
4 5
4
3 5 1 3
Vòng tròn: 3→5→1→3, qua 3 thành phố phân biệt.
3 2
1 2
2 3
IMPOSSIBLE Đồ thị là cây — không có chu trình.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0