Sắp xếp topo
Đề bài
Mô tả
Cho đồ thị có hướng gồm đỉnh đánh số từ đến và cung; cung thứ đi từ đỉnh tới đỉnh . Có thể có cung từ một đỉnh tới chính nó và nhiều cung giữa cùng một cặp đỉnh.
Hãy sắp xếp tất cả các đỉnh thành một dãy sao cho với mọi cung , đỉnh đứng trước đỉnh trong dãy. Nếu không thể sắp xếp như vậy, hãy thông báo.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên , .
- dòng tiếp theo, dòng thứ chứa hai số nguyên .
Dữ liệu ra
Nếu sắp xếp được, in ra trên một dòng số nguyên phân biệt từ đến là dãy đỉnh tìm được, cách nhau bởi dấu cách. Nếu có nhiều dãy thỏa mãn, in ra dãy bất kỳ.
Nếu không sắp xếp được, in ra -1.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 7 5 2 1 2 2 3 6 3 1 4 4 3 5 6 |
1 5 4 2 6 3 | Mọi cung đều đi từ trái sang phải trong dãy. Các dãy khác như 5 6 1 2 4 3 cũng được chấp nhận. |
| 4 4 1 2 2 3 3 4 4 2 |
-1 | Các cung tạo thành chu trình: đỉnh nào trong ba đỉnh này đứng đầu dãy thì cung đi vào nó đều bị ngược chiều. |
Bình luận