trang chủ / đề bài / icpcwf14_e

Rút gọn mê cung

Đề bài

Mô tả

Jay điều hành một khu hội chợ nhỏ với nhiều trò chơi và điểm tham quan. Không may, thời buổi khó khăn. Một tai nạn tàu lượn siêu tốc gần đây, vụ ngập nước trong nhà vệ sinh và một sự cố đáng tiếc với chú hề đã khiến hội chợ của Jay mang tiếng xấu. Khách trả tiền ít đi, doanh thu giảm, anh cần cắt giảm chi phí để trụ lại.

Một trong những điểm tham quan lớn nhất của hội chợ là một mê cung rộng lớn, rối rắm. Mê cung gồm nhiều phòng hình tròn nối với nhau bằng các hành lang hẹp, ngoằn ngoèo. Khách rất thích bị lạc trong đó và cố vẽ lại bản đồ. Jay để ý rằng có thể một số phòng thực chất giống hệt nhau. Nếu vậy, anh có thể thu nhỏ mê cung mà không ai nhận ra.

Hai phòng A và B được gọi là thực chất giống nhau nếu khi bị thả vào phòng A hoặc phòng B (và bạn biết bản đồ mê cung), bạn không thể biết mình bắt đầu ở A hay ở B chỉ bằng cách khám phá mê cung. Các lối ra hành lang được bố trí cách đều nhau quanh mỗi phòng, và bạn không thể đánh dấu hay để lại bất cứ thứ gì trong phòng (đặc biệt, bạn không thể biết mình đã từng vào một phòng hay chưa). Đặc điểm nhận dạng duy nhất của một phòng là số lối ra của nó. Các hành lang cũng đủ ngoằn ngoèo để không phân biệt được với nhau, nhưng khi vào một phòng, bạn biết mình vừa đi ra từ hành lang nào, nên có thể định hướng phần nào nhờ thứ tự xuất hiện của các hành lang quanh phòng.

Jay nhờ Hiệp hội Mê cung Hội chợ giúp đỡ, và đó chính là bạn! Hãy viết chương trình xác định tất cả các nhóm phòng thực chất giống nhau trong mê cung.

Hình dưới là mê cung trong ví dụ thứ nhất (chỉ thể hiện các hành lang, không thể hiện thứ tự các lối ra quanh mỗi phòng).

graph layout=circle
1 2
1 4
2 3
2 5
3 4
4 6
5 6
7 8
7 9
8 9
10 11
10 13
11 12
12 13

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n, số phòng của mê cung. Các phòng được đánh số từ 1 tới n.

Tiếp theo là n dòng, lần lượt mô tả từng phòng theo thứ tự. Mỗi dòng gồm một số nguyên k, cho biết phòng này có k hành lang, rồi k số nguyên phân biệt là các phòng mà từng hành lang nối tới, liệt kê theo chiều kim đồng hồ bắt đầu từ một vị trí tùy ý.

Dữ liệu ra

In ra mỗi nhóm cực đại các phòng thực chất giống nhau trên một dòng (bỏ qua các nhóm chỉ có 1 phòng), gồm số hiệu các phòng trong nhóm theo thứ tự tăng dần. Các nhóm được sắp xếp theo số hiệu phòng nhỏ nhất của nhóm. Nếu không có nhóm nào, in ra none.

Ràng buộc

  • 1≤n≤100.
  • 0≤k<100.
  • Không phòng nào có hành lang nối tới chính nó.

Ví dụ

Input Output Giải thích
13
2 2 4
3 1 3 5
2 2 4
3 1 3 6
2 2 6
2 4 5
2 8 9
2 7 9
2 7 8
2 11 13
2 10 12
2 11 13
2 10 12
2 4
5 6
7 8 9 10 11 12 13
Mê cung trong hình. Phòng 1 và 3 có cùng các phòng kề nhưng không giống nhau, vì thứ tự theo chiều kim đồng hồ của các lối ra quanh phòng 2 và 4 phân biệt được chúng. Các phòng 7 tới 13 đều có 2 lối ra và mọi phòng đi tới cũng có 2 lối ra, nên không thể phân biệt.
6
3 3 4 5
0
1 1
1 1
2 1 6
1 5
none Phòng 3 và 4 cùng có một lối ra dẫn tới phòng 1, nhưng từ phòng 1 đi theo chiều kim đồng hồ, lối sau lối dẫn về phòng 3 là lối tới phòng 4 (một lối ra), còn lối sau lối dẫn về phòng 4 là lối tới phòng 5 (hai lối ra).

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