Bài này minh làm như sau:
B1. Tìm đường đi S,x1,x2,..xk,T
B2. Xét tất cả các xi, i=1,2,..,k
2.1. Loại bỏ đỉnh xi khỏi đồ thị
2.2. Tìm đường đi từ S --> T
Nếu không có đường đi thì xi là nút xung yếu.

Kết quả: 80đ.
Ai chỉ giúp em Test sai với!!!

Cách này ko phải sai mà là bị TLE bạn ạ

Mình xem kết quả chạy chỉ có 0.6s

Đó là thời gian chạy những test không bị TLE
Những test bị TLE thì sẽ bị ngắt giữa chừng nên không biết đc chạy mất bao lâu

Vậy à, bây giờ thì em đã hiểu. Ai có thuật toán tốt chỉ giáo cho mình với!!!

cũng có thể cải tiến thuật toán của bạn 1 chút cho nó thành 100 như thế này :P
*bước 1 : với mỗi đỉnh là nút xung yếu trên đường đi từ s -->t.bạn gán luôn s bằng đỉnh đó để bước tìm đường tiếp theo có thể giảm đi tính toán --->ăn thêm 1 test là 90
*bước 2 : cố gắng xét + vứt bỏ những đỉnh chắc chắn ko là nút xung yếu trên đường đi bằng 1 vài trò bựa bựa khác :P
---> ăn thêm 1 test là 100 :P

vài trò bựa bựa thỉnh thoảng hữu ích ra phết ấy chứ nhỉ

Cảm ơn bạn Quỳnh!
+ Mình làm theo cải tiến 1 và đã đạt 90đ.
+ Vài trò bựa bựa của bạn là gì thì mình bó tay, chưa thể nào nghĩ ra!

Bài này có thuật giải dùng DFS và BFS với độ phức tạp O(M+N),bạn có thể sang topic bàn luận để tham khảo hoặc hỏi cách DFS của anh Khúc Tuấn.
Cách của bạn mình nghĩ là bị TLE

Mình xin phép post thuật toán tốt bên topic bàn luận ở đây nhé!!!
===========================================================================================
Bài 2: (của bạn Quang Vũ)
1. Tìm 1 đường đi bất kỳ từ s đến t, s=u0u1u2..uk=t
Gán nhãn cho các đỉnh này lần lượt là 0,1,2,..,k
Nhận xét: các đỉnh thỏa mãn phải thuộc đường đi này
2. Với mọi đỉnh u của đồ thị, tính f[u] với ý nghĩa
f[u] = đỉnh có nhãn lớn nhất đến được từ u mà không sử dụng các cạnh thuộc đường đi trên
3. Điều kiện để đỉnh ui thõa mãn là:
với mọi j < i, f[uj] <= i

Để tính f, có thể dùng dfs.
Độ phức tạp O(n+m).
===========================================================================================
Quá hay!!!