trang chủ / bài tập / roundtrip

Vòng Tròn

Đề bài

Mô tả

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 nm.
  • m dòng tiếp theo: mỗi dòng gồm hai số nguyên ab — 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

  • 1n105
  • 1m2×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.400 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.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0