Xin lỗi bạn, đoạn trên chỗ vấn đề 2 mình viết chưa chuẩn lắm. Cái sai của bạn là không cập nhật đúng cho biến ll.
Ví dụ test đơn giản này thôi:
3 1
1 2 1
2 3 1
1 2
-Gọi dfs(1,i):
-- thấy đỉnh 2 kề đỉnh 1 bạn tăng ll và gọi dfs(2,i) (lúc này ll = 1):
--- thấy đỉnh 3 kề đỉnh 2 bạn tăng ll và gọi dfs(3,i) (lúc này ll = 2):
---- thấy đỉnh 2 kề đỉnh 3 bạn tăng ll (ll = 3) và gọi dfs(2,i), nhưng vì mau[2]=1 nên hàm dfs(2,i) này sẽ return luôn, sau đó bạn thấy 2 là đích đến, bạn cập nhật e = ll (tức là e = 3), SAU ĐÓ EXIT LUÔN mà không cập nhật lại giá trị cho ll.
Chỗ viết hoa là chỗ bạn làm sai, bạn exit luôn thì biến ll sau đó sẽ không còn giữ giá trị đúng nữa, do đoạn code ll=ll-l[b] bị bỏ qua.
Xét tiếp:
--- dfs(3,i) bị exit, quay lại dfs(2,i) (lúc này ll = 3, đáng lẽ nó phải = 2)
-- dfs(2,i) trừ ll đi 1 (ll = 2, đáng lẽ phải là 1) và return, quay lại dfs(1,i)
- dfs(1,i) thực hiện tiếp, lúc này thấy rằng 2 là đích đến, cập nhật e = ll (tức là e = 2), nhưng vì ll sai nên e cũng sai.
Tại sao lại bị như vậy, là do bạn dfs đến toàn bộ các đỉnh, vậy nên khi dfs đến một đỉnh kề với đỉnh đích bạn đều gán e=ll và exit luôn, tức là ll sẽ bị mất giá trị đúng, mà lần gán e=ll cuối cùng mới là gán đúng kết quả (mấy lần trước đó đều gán sai kết quả), mà lúc đó thì ll đã bị sai rồi. Nếu chỉ có 1 đỉnh kề với đích thì sẽ chạy đúng vì khi đó e=ll chỉ được gán 1 lần duy nhất, mà lúc đó thì ll chưa bị sai.
Giải pháp ở đây sẽ theo 2 hướng:
- đảo dfs xuống sau đoạn xét e=ll: để đảm bảo rằng đỉnh đích sẽ không bị gọi dfs, do bạn đến đỉnh đích là bạn gán e=ll rồi exit luôn. Sau đó ll có bị sai thì cũng không ảnh hưởng vì chắc chắn e không bị gán lại nữa (vì các đỉnh khác mà kề với đỉnh đích - tức là các đỉnh có thể gán e=ll đều không bị gọi dfs, do đỉnh đích không được gọi dfs).
- xóa exit ở chỗ e=ll đi: điều này đảm bảo ll luôn đúng, và vì lần gán e=ll cuối cùng là lần gán cho kết quả đúng nên sẽ không bị sai.