CTDL&GT bài 18.A9 CTDL&GT bài [Graph]. DFS trên đồ thị vô hướng.


LÀM BÀI

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

[Graph]. DFS trên đồ thị vô hướng.

Cho đồ thị vô 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 DFS(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 DFS(s). Chú ý trong quá trình mở rộng các đỉnh của thuật toán DFS 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 2
1 2
2 5
3 4
3 5
4 5
1 4
2 3
2 4
1 3
Dữ liệu ra
2 1 3 4 5

Comments

There are no comments at the moment.

Zalo