Thứ tự công việc nhỏ nhất
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một dây chuyền sản xuất gồm $N$ công việc đánh số từ $1$ đến $N$ và $M$ ràng buộc thứ tự. Mỗi ràng buộc $(u, v)$ yêu cầu công việc $u$ phải thực hiện trước công việc $v$.
Nếu có nhiều thứ tự thực hiện hợp lệ, hãy tìm thứ tự có thứ tự từ điển nhỏ nhất. Nếu không thể hoàn thành tất cả công việc (tồn tại chu trình), in ra -1.
Dữ liệu vào
- Dòng đầu 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ố $u, v$ ($1 \le u, v \le N$, $u \ne v$).
Dữ liệu ra
In ra $N$ số nguyên là thứ tự từ điển nhỏ nhất (cách nhau bởi dấu cách), hoặc -1 nếu không tồn tại thứ tự hợp lệ.
Ví dụ
| Input | Output |
|---|---|
| 4 3 2 1 3 1 3 4 |
2 3 1 4 |
| 3 3 1 2 2 3 3 1 |
-1 |
Giới hạn
$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion