Những chuyến tàu của Hobson
Đề bài
Mô tả
Ông Hobson đã thôi điều hành trại ngựa và chuyển sang đầu tư vào một loại hình giao thông hiện đại hơn: tàu hỏa. Ông xây dựng một mạng lưới đường sắt gồm ga. Tuy vậy, ông vẫn giữ cam kết giải phóng hành khách khỏi gánh nặng có quá nhiều lựa chọn: từ mỗi ga, hành khách có thể đi tàu tới đúng một ga khác. Một chuyến đi như vậy được gọi là một chặng. Lưu ý rằng chặng là hành trình một chiều, và có thể không quay lại được.
Hobson cũng chỉ bán đúng một loại vé, cho phép hành khách đi tối đa chặng trong một hành trình. Ở lối ra của mỗi ga có một máy đọc vé tự động (chỉ một máy, để hành khách không phải chọn dùng máy nào). Máy kiểm tra rằng khoảng cách từ ga xuất phát tới ga cuối cùng không vượt quá chặng.
Mỗi máy đọc vé phải được nạp danh sách các ga xuất phát hợp lệ, nhưng danh sách càng tốn bộ nhớ thì máy càng đắt. Hãy giúp Hobson xác định, với mỗi ga , số ga (tính cả chính ) mà từ đó hành khách có thể tới bằng không quá chặng.
Hình dưới minh họa ví dụ thứ nhất: mỗi đỉnh là một ga, nhãn cạnh mỗi đỉnh là danh sách các ga xuất phát được nạp vào máy đọc vé của ga đó khi .
graph directed
1 2
2 3
3 4
4 5
5 4
6 3
label 1 {1}
label 2 {1,2}
label 3 {1,2,3,6}
label 4 {2,3,4,5,6}
label 5 {3,4,5}
label 6 {6}
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó là số ga và là số chặng tối đa được đi bằng một vé.
Tiếp theo là dòng, dòng thứ chứa một số nguyên : ga có thể tới được từ ga bằng một chặng.
Dữ liệu ra
In ra dòng, dòng thứ chứa số ga mà từ đó có thể tới ga bằng không quá chặng.
Ràng buộc
- .
- .
- và .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 2 3 4 5 4 3 |
1 2 4 5 3 1 |
Mạng lưới trong hình trên. Ví dụ ga tới được từ các ga (ga qua , ga qua , ga đi một chặng), còn ga cần chặng nên không được tính. |
| 5 3 2 3 1 5 4 |
3 3 3 2 2 |
Hai vòng tách rời và . Mỗi ga tới được từ mọi ga cùng vòng của nó. |
Bình luận