Thứ Tự Topo Từ Điển Nhỏ Nhất

General
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved