Đường đi dài nhất trên đồ thị có hướng

Buổi 73-74 — Virtual CF Dynamic Programming Graphs
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một đồ thị có hướng gồm $n$ đỉnh và $m$ cạnh. Nếu đồ thị là đồ thị không có chu trình (DAG), hãy tìm độ dài (số cạnh) của đường đi có hướng dài nhất trong đồ thị. Nếu đồ thị có chứa 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ố nguyên $u, v$ mô tả cạnh có hướng từ $u$ đến $v$.
Dữ liệu ra
  • Một số nguyên duy nhất là độ dài đường đi dài nhất, hoặc -1 nếu có chu trình.
Ví dụ
Input Output
4 5
1 2
1 3
3 2
2 4
3 4
3
Giới hạn
  • $1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$
Draft saved