Nguồn:
Mr Kiên
Cho đồ
thị vô hướng gồm N đỉnh và M cạnh, độ dài của mỗi cạnh bằng 1.
Tìm độ dài đường đi ngắn nhất từ đỉnh 1 đến cách đỉnh còn lại của đồ thị.
Dữ liệu vào: Từ tệp văn bản BFS1.INP
+ Dòng
đầu tiên gồm hai số nguyên dương N và M (1≤N, M≤105)
+ M
dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương x và y, chỉ 1 cạnh nối giữa
hai đỉnh x và y
Dữ liệu ra: ghi vào tệp văn bản
BFS1.OUT
+ In ra N dòng, dòng thứ i là độ
dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.
+ Nếu không thể đi từ 1 đến i,
in ra -1
Ví dụ:
|
BFS1.INP
|
BFS1.OUT
|
|
5 4
1 2
2 3
2 4
3 4
|
0
1
2
2
-1
|
