Mình xin chia sẻ lời giải bài này như sau:

Đầu tiên, ta sẽ thực hiện một phép biến đổi đồ thị đã cho thành đồ thị tương tự nhưng vẫn đảm bảo không thay đổi kết quả của bài toán

Cụ thể như sau:

Ứng với mỗi cạnh trong đồ thị ban đầu, sẽ là \(1\) đỉnh của đồ thị sau khi biến đối. (Các bạn có thể xem hình bên dưới)

Như vậy bài toán đã cho quy về bài toán: tìm khoảng cách từ đỉnh \(1\) đến tất cả các đỉnh => Đây chính bài toán tương tự bài bfs cơ bản.

Gọi mảng \(d[]\) là mảng trong đó \(d[i]\) chính là khoảng cách từ đỉnh \(i\) đến đỉnh \(1\). Khi đó ta chỉ cần in ra \(d[i]+1\) với mỗi \(i\) chạy từ \(1\) đến \(n\)

Như vậy là bài toán đã được giải quyết xong !

Ps:

• Nếu có gì thắc mắc, các bạn có thể comment.

• Các bạn có thể tham khảo code của mình tại đây Link