Thứ tự duyệt DFS
Cho đồ thị vô hướng có $n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ 1 đến $n$. Cạnh thứ $i$ nối 2 đỉnh $u_i$ và $v_i$.
Hãy in ra thứ tự duyệt đồ thị bằng DFS. Nếu gặp nhiều đỉnh kề, thăm đỉnh theo thứ tự tăng dần của chỉ số. Nếu có nhiều đỉnh xuất phát, xuất phát từ đỉnh có chỉ số nhỏ nhất.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $n, m \ (1\le n,m \le 10^5)$;
- $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i \ (1\le u_i, v_i \le n; u_i \neq v_i)$.
Dữ liệu đảm bảo không có hai cạnh nào chúng kết nối hai đỉnh.
Kết quả
- In ra $n$ số nguyên là thứ tự duyệt đồ thị bằng DFS. Mỗi số nguyên cách nhau bởi một dấu cách.
Ví dụ
Ví dụ 1
input
5 6
1 4
2 1
1 3
4 5
2 4
1 5
output
1 2 4 5 3
Comments