Thứ Tự Topo Từ Điển Nhỏ Nhất
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ công việc đánh số từ $1$ đến $N$ và $M$ điều kiện ràng buộc dạng $(u, v)$, nghĩa là công việc $u$ phải được hoàn thành trước công việc $v$.
Hãy tìm một thứ tự thực hiện toàn bộ $N$ công việc sao cho thỏa mãn mọi điều kiện ràng buộc và có thứ tự từ điển nhỏ nhất. Nếu không tồn tại thứ tự hợp lệ (do có chu trình phụ thuộc), hãy in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
- Nếu tồn tại, in ra $N$ số nguyên cách nhau bởi dấu cách là thứ tự thực hiện có thứ tự từ điển nhỏ nhất. Ngược lại, in ra
-1.
Ví dụ
| Input | Output |
|---|---|
| 4 3 2 1 3 1 1 4 |
2 3 1 4 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$
Community Discussion