Elearning CodePath – CTP Online Judge

Duyệt Đồ thị theo Chiều sâu

DFS Traversal

🟢 Easy #Graph

### 📝 Bài toán

Cho đồ thị vô hướng $G=(V, E)$ gồm $N$ đỉnh và $M$ cạnh. Đồ thị được đảm bảo là liên thông.

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

**Quy tắc duyệt:**
* Thứ tự duyệt DFS phải được thể hiện bằng cách in ra đỉnh ngay khi nó được thăm lần đầu tiên.
* Giả định rằng khi duyệt các đỉnh kề, thứ tự duyệt không được quy định rõ. Tuy nhiên, để có kết quả xác định như ví dụ, cần duyệt theo một thứ tự nhất định (ví dụ: theo thứ tự đỉnh tăng dần).

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

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

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

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

Gồm nhiều dòng, mỗi dòng in ra một số nguyên là thứ tự các đỉnh được thăm trong quá trình duyệt DFS.

---
### 🏷 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