Thứ tự duyệt BFS


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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 BFS. 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 BFS. Mỗi số nguyên cách nhau bởi một dấu cách.

Ví dụ

Ví dụ 1

input

5 7
1 3
1 4
2 1
2 3
4 5
2 4
1 5

output

1 2 3 4 5

Comments

There are no comments at the moment.