Phát hiện đường cụt
Đề bài
Mô tả
Hội đồng thành phố quê bạn quyết định cải thiện việc đặt biển báo giao thông, đặc biệt là biển báo đường cụt. Họ đưa cho bạn bản đồ đường phố và bạn phải xác định cần đặt biển ở đâu để đánh dấu các đường cụt. Họ muốn dùng càng ít biển càng tốt.
Bản đồ gồm một tập các địa điểm được nối với nhau bởi các con đường hai chiều. Quy tắc sau mô tả cách thu được một phương án đặt biển báo đường cụt đầy đủ. Xét một con đường nối địa điểm với một địa điểm khác. Lối vào phía của được đặt biển báo đường cụt nếu sau khi đi vào từ , không thể quay trở lại mà không quay đầu xe. Quay đầu xe là một lượt quay độ, đổi ngược ngay lập tức hướng đi.
Để tiết kiệm chi phí, bạn quyết định không đặt các biển báo thừa, theo quy tắc sau. Xét một con đường có biển báo đường cụt ở lối vào phía và một con đường khác có biển báo đường cụt ở lối vào phía . Nếu sau khi đi vào từ , có thể đi tới và đi vào (từ phía ) mà không quay đầu xe, thì biển báo ở lối vào phía của là thừa.
Hình dưới minh họa hai ví dụ. Các con đường tô đỏ là những con đường được đặt biển báo không thừa; vị trí của biển (đầu nào của con đường) ghi trong cột Giải thích của bảng ví dụ.
graph 6 5 1 2 1 3 2 3 4 5 5 6 highlight red 4-5 5-6
graph 8 8 1 2 1 3 2 3 3 4 1 5 1 6 6 7 6 8 highlight red 1-5 1-6 3-4
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó là số địa điểm và là số con đường.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và cho biết có một con đường hai chiều nối địa điểm và địa điểm . Mọi cặp địa điểm trong dữ liệu vào đều khác nhau.
Dữ liệu ra
Dòng đầu tiên in ra , số biển báo đường cụt được đặt.
Mỗi dòng trong dòng tiếp theo in ra hai số nguyên và , cho biết một biển báo đường cụt được đặt ở lối vào phía của con đường nối hai địa điểm và . Các dòng mô tả biển báo phải được sắp xếp tăng dần theo , nếu bằng nhau thì tăng dần theo .
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 5 1 2 1 3 2 3 4 5 5 6 |
2 4 5 6 5 |
Từ các địa điểm luôn có thể đi vòng quanh tam giác để quay lại. Đi vào đường - từ thì phải quay đầu ở mới về được , nên lối vào phía có biển; tương tự lối vào phía của đường -. Biển ở lối vào phía của hai con đường này là thừa: từ đi vào đường - có thể tới rồi đi vào đường -. |
| 8 8 1 2 1 3 2 3 3 4 1 5 1 6 6 7 6 8 |
3 1 5 1 6 3 4 |
Biển đặt ở lối vào phía của các đường -, - và lối vào phía của đường -. Biển ở lối vào phía của các đường -, - là thừa vì có thể đi từ vào đường - rồi đi tiếp vào chúng. |
Bình luận