Đường Đi Dài Nhất Trên DAG Rút Gọn

Buổi 43 — SCC (Tarjan) & 2-SAT Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị có hướng gồm N đỉnh và M cạnh. Xây dựng đồ thị rút gọn (condensation DAG). Trọng số mỗi đỉnh trong DAG rút gọn bằng số đỉnh trong SCC tương ứng. Tìm đường đi dài nhất trên DAG rút gọn (tổng trọng số đỉnh lớn nhất).

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
  • M dòng tiếp theo: u v
Dữ liệu ra
  • Một số nguyên: tổng trọng số lớn nhất trên đường đi trong DAG rút gọn.
Ví dụ
Input Output
7 8\n1 2\n2 3\n3 1\n4 5\n5 4\n6 7\n7 6\n3 4 7
Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved