Elearning CodePath – CTP Online Judge

Duyệt Đồ thị theo Chiều rộng

IMP002

🟢 Easy #Graph #BFS/DFS #Connected Components

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho đồ thị có $N$ đỉnh và $M$ cạnh. Đồ thị là vô hướng (hoặc có hướng và yêu cầu duyệt cả hai chiều). Dựa trên ví dụ, đây là đồ thị vô hướng.

Yêu cầu: Viết chương trình thực hiện duyệt đồ thị theo chiều rộng (BFS) bắt đầu từ đỉnh nguồn $S=1$ và ghi ra thứ tự các đỉnh được thăm.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `bfs.inp`:

* Dòng 1: Hai số nguyên $N$ và $M$.
* $M$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $U, V$ mô tả một cạnh giữa đỉnh $U$ và $V$.

Giới hạn:
* $1 \le N, M \le 100$.
* $1 \le U, V \le 100$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `bfs.out` thứ tự các đỉnh được thăm trong quá trình duyệt BFS, mỗi đỉnh trên một dòng hoặc cách nhau bởi dấu cách (dựa trên ví dụ, nên in cách nhau bởi dấu cách hoặc xuống dòng). Ta chọn in trên **một dòng, cách nhau bởi dấu cách**.

---
### 🏷 Phân Subtask

Do giới hạn $N, M$ rất nhỏ ($N, M \le 100$), thuật toán $O(N^2)$ hoặc $O(N+M)$ đều hoạt động tốt. Phân subtask dựa trên giới hạn nhỏ.

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N, M \le 50$ | $50\%$ |
| 2 | $N, M \le 100$ | $50\%$ |

---

✅ Đã AC: 0 / 0 submissions