Atcoder Educational DP Contest G - Longest Path
Xem dạng PDF
Cho đồ thị có hướng ~G~ có ~N~ đỉnh và ~M~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~N~, và cạnh có hướng thứ ~i~ ~(1 \leq i \leq M)~ đi từ đỉnh ~x_i~ tới đỉnh ~y_i~.
Đảm bảo rằng đồ thị ~G~ không có chu trình.
Tìm độ dài đường đi có hướng dài nhất trong đồ thị ~G~, quy ước rằng: độ dài của một đường đi có hướng là số cạnh nằm trên đường đi đó.
Input
Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~, lần lượt là số đỉnh và số cạnh của đồ thị đã cho. ~(2 \leq N \leq 10^5 , 1 \leq M \leq 10^5 ) ~
Dòng thứ ~i~ trong số ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~, biểu diễn cho cạnh thứ ~i~ của đồ thị.
Đảm bảo rằng tất cả các cạnh ~(x_i, y_i)~ bất kì đều phân biệt và đồ thị ~G~ không có chu trình.
Outout
In ra độ dài của đường đi có hướng dài nhất trong đồ thị ~G~.
Sample 1
Input
4 5
1 2
1 3
3 2
2 4
3 4
Output
3
Giải thích
Đường màu đỏ trong hình dưới đây là đường đi dài nhất:
Sample 2
Input
6 3
2 3
4 5
5 6
Output
2
Giải thích
Đường màu đỏ trong hình dưới đây là đường đi dài nhất:
Sample 3
Input
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
Output
3
Giải thích
Đường màu đỏ trong hình dưới đây là đường đi dài nhất:
Bình luận
orz
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Hết cứu
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
xin_loi;
nó bị lấy acc bl linh tinh á:))
rất xin lỗi ạ. ko phải mình bl đâu bạn.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.