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 và được gọi là thực chất giống nhau nếu khi bị thả vào phòng hoặc phòng (và bạn biết bản đồ mê cung), bạn không thể biết mình bắt đầu ở hay ở 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 , số phòng của mê cung. Các phòng được đánh số từ tới .
Tiếp theo là 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 , cho biết phòng này có hành lang, rồi 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ó 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
- .
- .
- 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 và 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 và phân biệt được chúng. Các phòng tới đều có lối ra và mọi phòng đi tới cũng có 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 và cùng có một lối ra dẫn tới phòng , nhưng từ phòng đi theo chiều kim đồng hồ, lối sau lối dẫn về phòng là lối tới phòng (một lối ra), còn lối sau lối dẫn về phòng là lối tới phòng (hai lối ra). |
Bình luận