CTDL> bài 18.A12 CTDL> bài [Graph].BFS trên đồ thị có hướng.
[Graph].BFS trên đồ thị có hướng.
Cho đồ thị có hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy thực hiện in ra danh sách các đỉnh được duyệt theo thuật toán BFS(s).
Input Format
Dòng đầu tiên là 2 số n và m và s, tương ứng với số lượng đỉnh, cạnh của đồ thị và đỉnh bắt đầu duyệt. Các đỉnh của đồ thị được đánh số từ 1 tới n. m dòng tiếp theo mỗi dòng chứa đỉnh u, v (u != v) tương ứng với một cạnh của đồ thị. (1<=s<=n<=1000; 1<=m<=n*(n-1)/2)
Constraints
.
Output Format
In ra các đỉnh được duyệt theo thuật toán BFS(s). Chú ý trong quá trình mở rộng các đỉnh của thuật toán BFS luôn lựa chọn duyệt các đỉnh có thứ tự nhỏ hơn trước.
Ví dụ:
Dữ liệu vào
5 9 1
1 2
1 3
1 4
2 1
2 4
2 5
3 4
3 5
4 5
Dữ liệu ra
1 2 3 4 5
Comments