DFS - Tìm kiếm theo chiều sâu
Dữ liệu vào: Standard input
Dữ liệu ra: Standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: Ngapt

Cho đồ thị vô hướng G gồm n đỉnh và m cạnh  (2<=n<=100)

Hãy chỉ ra đường đi ưu tiên chiều sâu từ s đến t. (1<=s,t<=n)

Inp:

Dòng đầu ghi 2 số nguyên dương n m

m dòng tiếp theo, mỗi dòng ghi 2 số u v biểu thị có cạnh nối từ u đến v

Dòng cuối cùng ghi 2 số nguyên dương s t

Out:

Thứ tự các đỉnh trên đường đi ưu tiên chiều sâu từ s đến t.

Nếu không có đường đi từ s đến t ghi ra NO

 

Ví dụ

  • input
    3 1
    3 2
    2 1
    output
    NO
  • input
    5 5
    1 2
    2 3
    4 2
    4 5
    3 5
    5 1
    output
    5 3 2 1

P/s: Hãy cài đặt bài toán trên bằng cả 3 cách biểu diễn (lưu) đồ thị để so sánh:

1, Ma trận kề

2, Danh sách cạnh

3, Danh sách kề

Back to Top