Em đang thử giải một bài toán trên CSES: CSES - Longest Flight Route
Tóm tắt đề bài: cho một đồ thị có hướng không chu trình, n đỉnh và m cạnh. Cho biết độ dài đường đi dài nhất từ đỉnh 1 đến đỉnh n, và đưa ra truy vết
Em đã thử giải bài này bằng DFS, và đây là code của em: Submission
Tuy nhiên em bị TLE ở testcase số 15, 17 và 18, và em chưa biết mình sai ở đâu
Em mong mọi người giúp em để em có cách làm đúng ạ 
Bài này chắc là nên dùng bfs kết hợp với queue mà xử thôi
Mỗi lần có đường đi từ 1 đến x tốt hơn (theo đề bài là dài hơn) thì thêm vào x queue, lần lượt duyệt các phần tử trong queue, và cứ thế cho tới khi queue rỗng
Update: vấn đề truy viết thì bạn có thể dùng một cái mảng hay vector để ghi lại path lúc đang duyệt queue
UPDATE: Sau cùng thì em cũng đã tìm ra lời giải thích hợp cho bài toán này !
Trước tiên, xét về 3 cách tiếp cận có thể nghĩ tới đầu tiên cho bài toán:
Cách 1 và 2:
Về nguyên lý, cách 1 và cách 2 không hề sai: Mỗi khi tìm được một con đường có độ dài lớn hơn, chúng ta đưa đỉnh đó vào danh sách duyệt, để liên tục tối ưu, tìm ra con đường dài nhất.
Tuy nhiên, thuật toán lại vô tình làm tăng ĐPT: Giả sử chúng ta tìm được dp[x] là độ dài lớn nhất đi từ đỉnh 1 đến đỉnh x, sau đó lại tìm được một đỉnh u -> x mà dp[x] < dp[u] + 1. Điều này tương đương với việc, ta lại phải DFS (hoặc BFS) trở lại chính những đỉnh ta đã tối ưu cho dp[x], chỉ vì muốn tìm ra đường đi dài nhất có thể.
Trường hợp xấu nhất khi DFS (hoặc BFS) lại những đỉnh đã thăm nhiều lần như vậy, có thể khiến ĐPT tăng tới xấp xỉ O(n^2) (!!)
Cách 3:
Đối với cách 3 thì có vẻ thông minh hơn: Gần giống thuật Greedy, Dijkstra biến thể sẽ liên tục tối ưu với những đỉnh “có hi vọng tối ưu nhất”, vì thế phần nào có thể làm giảm ĐPT thuật toán trong trường hợp xấu nhất của 2 cách trên
Nhưng Dijkstra biến thể vẫn có 2 vấn đề:
Vấn đề 1 -> Dijkstra gặp trường hợp xấu nhất
Vấn đề 2 -> Người ta dựa trên tính chất này để sinh test các đỉnh ngược chiều thứ tự từ điển, Dijkstra sẽ hoạt động đúng như trường hợp xấu nhất: thăm lại tất cả những đỉnh đã thăm
-> ĐPT vẫn có thể xấp xỉ O(n^2)
Cách giải quyết: Dùng sắp xếp topo, để đảm bảo “đỉnh này luôn được thăm trước đỉnh kia”.
Mỗi đỉnh và cạnh chỉ được xét đến đúng 1 lần trong thứ tự topo
-> ĐPT O(n+m)
Lưu ý là ta sẽ lưu thêm một mảng inchain[x], với ý nghĩa là đỉnh x được đi tới từ đỉnh 1
Solution
https://algs4.cs.princeton.edu/44sp/AcyclicLP.java
relax các cạnh có trọng số -1 (ko cần -1 cũng được) của các đỉnh đã được sắp xếp theo thứ tự topo, O(V+E) thôi 
vd tìm đường đi dài nhất từ 8 tới 9
1 → 2 → 3
↑ ↓
4 5 → 6
↑ ↑ ↓
7 ← 8 → 9
sắp xếp topo thì thứ tự các đỉnh có thể là 8 7 5 4 1 2 3 6 9
relax các cạnh:
ban đầu:
1(0) → 2(0) → 3(0)
↑ ↓
4(0) 5(0) → 6(0)
↑ ↑ ↓
7(0) ← 8(0) → 9(0)
relax các cạnh của 8: giá trị của vert7 từ 0 thành 1, vert5 từ 0 thành 1, vert9 từ 0 thành 1
1(0) → 2(0) → 3(0)
↑ ↓
4(0) 5(1) → 6(0)
↑ ↑ ↓
7(1) ←*8(0) → 9(1)
relax các cạnh của 7: giá trị vert4 từ 0 thành 2
1(0) → 2(0) → 3(0)
↑ ↓
4(2) 5(1) → 6(0)
↑ ↑ ↓
*7(1) ← 8(0) → 9(1)
relax các cạnh của 5: giá trị vert6 từ 0 thành 2
1(0) → 2(0) → 3(0)
↑ ↓
4(2) *5(1) → 6(2)
↑ ↑ ↓
7(1) ← 8(0) → 9(1)
relax các cạnh của 4: giá trị vert1 từ 0 thành 3
1(3) → 2(0) → 3(0)
↑ ↓
*4(2) 5(1) → 6(2)
↑ ↑ ↓
7(1) ← 8(0) → 9(1)
relax các cạnh của 1: giá trị vert2 từ 0 thành 4
*1(3) → 2(4) → 3(0)
↑ ↓
4(2) 5(1) → 6(2)
↑ ↑ ↓
7(1) ← 8(0) → 9(1)
relax các cạnh của 2: giá trị vert3 từ 0 thành 5
1(3) →*2(4) → 3(5)
↑ ↓
4(2) 5(1) → 6(2)
↑ ↑ ↓
7(1) ← 8(0) → 9(1)
relax các cạnh của 3: giá trị vert6 từ 2 thành 6
1(3) → 2(4) →*3(5)
↑ ↓
4(2) 5(1) → 6(6)
↑ ↑ ↓
7(1) ← 8(0) → 9(1)
relax các cạnh của 6: giá trị vert9 từ 1 thành 7
1(3) → 2(4) → 3(5)
↑ ↓
4(2) 5(1) →*6(6)
↑ ↑ ↓
7(1) ← 8(0) → 9(7)
relax các cạnh của 9:
1(3) → 2(4) → 3(5)
↑ ↓
4(2) 5(1) → 6(6)
↑ ↑ ↓
7(1) ← 8(0) →*9(7)
đã sx theo thứ tự topo rồi thì lúc relax cạnh update giá trị của các đỉnh đối diện khỏi cần so sánh luôn vì trọng số các cạnh ở đây bằng nhau 
nếu cùng graph này mà hỏi đi từ 5 tới 9 thì ban đầu giá trị khởi tạo = 0 ko đúng 
Vậy ban đầu nên khởi tạo giá trị invalid nào đó. Nếu đỉnh đang xét có giá trị invalid thì ignore nó đi:
ban đầu: khởi tạo tất cả giá trị của các vert là invalid (i), ngoại trừ vert 5 bắt đầu có giá trị là 0
1(i) → 2(i) → 3(i)
↑ ↓
4(i) *5(0) → 6(i)
↑ ↑ ↓
7(i) ← 8(i) → 9(i)
relax các cạnh của 8: 8 có giá trị invalid, bỏ qua
1(i) → 2(i) → 3(i)
↑ ↓
4(i) 5(0) → 6(i)
↑ ↑ ↓
7(i) ←*8(i) → 9(i)
relax các cạnh của 7: 7 có giá trị invalid, bỏ qua
1(i) → 2(i) → 3(i)
↑ ↓
4(i) 5(0) → 6(i)
↑ ↑ ↓
*7(i) ← 8(i) → 9(i)
relax các cạnh của 5: giá trị vert6 từ i thành 1
1(i) → 2(i) → 3(i)
↑ ↓
4(i) *5(0) → 6(1)
↑ ↑ ↓
7(i) ← 8(i) → 9(i)
relax các cạnh của 4: 4 có giá trị invalid, bỏ qua
1(i) → 2(i) → 3(i)
↑ ↓
*4(i) 5(0) → 6(1)
↑ ↑ ↓
7(i) ← 8(i) → 9(i)
relax các cạnh của 1: 1 có giá trị invalid, bỏ qua
*1(i) → 2(i) → 3(i)
↑ ↓
4(i) 5(0) → 6(1)
↑ ↑ ↓
7(i) ← 8(i) → 9(i)
relax các cạnh của 2: 2 có giá trị invalid, bỏ qua
1(i) →*2(i) → 3(i)
↑ ↓
4(i) 5(0) → 6(1)
↑ ↑ ↓
7(i) ← 8(i) → 9(i)
relax các cạnh của 3: 3 có giá trị invalid, bỏ qua
1(i) → 2(i) →*3(i)
↑ ↓
4(i) 5(0) → 6(1)
↑ ↑ ↓
7(i) ← 8(i) → 9(i)
relax các cạnh của 6: giá trị vert9 từ i thành 2
1(i) → 2(i) → 3(i)
↑ ↓
4(i) 5(0) →*6(1)
↑ ↑ ↓
7(i) ← 8(i) → 9(2)
relax các cạnh của 9:
1(i) → 2(i) → 3(i)
↑ ↓
4(i) 5(0) → 6(1)
↑ ↑ ↓
7(i) ← 8(i) →*9(2)
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?