#1621. Vết dầu loang (OIL)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một đồ thị vô hướng gồm N đỉnh và M cạnh. Giả sử có một vết dầu loang bắt đầu từ đỉnh S . Hãy xác định tất cả các đỉnh mà vết dầu có thể lan tới được (tức là các đỉnh có đường đi từ S ).

Dữ liệu:

  • Dòng đầu tiên chứa ba số nguyên N, M, S ( 1 \le N \le 1000, 0 \le M \le 10000, 1 \le S \le N ).
  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v mô tả một cạnh nối giữa đỉnh u và đỉnh v .

Kết quả:

  • Một dòng duy nhất liệt kê các đỉnh mà vết dầu lan tới được theo thứ tự tăng dần, các số cách nhau bởi một khoảng trắng.

Ví dụ:

Dữ liệu:

6 4 1
1 2
2 3
4 5
5 6

Kết quả:

1 2 3