Problem

1 /5


sắp xếp tô pô

Theory Click to read/hide

Thuật toán có thể được mô tả như sau:
Cho đồ thị có hướng có n đỉnh và m cạnh. Cần phải đánh số lại các đỉnh của nó sao cho mỗi cạnh dẫn từ đỉnh có số thấp hơn đến đỉnh có số cao hơn.
Nói cách khác, cần phải tìm một hoán vị của các đỉnh (thứ tự tô pô) tương ứng với thứ tự đã cho của tất cả các cạnh của đồ thị.
Chúng tôi sẽ sử dụng tìm kiếm theo chiều sâu (dfs(v))
Nếu chúng ta thêm đỉnh của mình vào đầu danh sách tại thời điểm thoát khỏi \(dfs(v)\) , thì cuối cùng trong danh sách này, bạn sẽ có được một kiểu sắp xếp tô pô.
Do đó, sắp xếp tô pô mong muốn — điều này được sắp xếp theo thứ tự thời gian thoát giảm dần.

Problem

Cho một đồ thị không trọng số có hướng. Cần phải sắp xếp nó theo cấu trúc liên kết.

Input: Dòng đầu tiên chứa 2 số tự nhiên n và m (1≤n≤105, 1≤m≤105) — lần lượt là số đỉnh và số cạnh của đồ thị. M dòng tiếp theo liệt kê các cạnh của đồ thị. Mỗi cạnh được cho bởi một cặp số — lần lượt là số đỉnh đầu và đỉnh cuối.
 
Đầu ra: In bất kỳ loại tô pô nào của đồ thị dưới dạng một chuỗi các số đỉnh. Nếu biểu đồ không thể được sắp xếp theo cấu trúc liên kết, in −1.
Dòng đầu tiên ghi số đỉnh N và số cạnh M. 

Ví dụ <đầu>
# Đầu vào Đầu ra
1 4 4
14
4 3
4 2
3 2
1 4 3 2