Đường đi dài nhất trên đồ thị có hướng
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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
-1nế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$
Community Discussion