Elearning CodePath – CTP Online Judge

Kiểm tra Kết nối Mạng

IMP001

🟢 Medium #Graph #Shortest Path #BFS/DFS #Connected Components

### 📌 Thông tin chung

Các bài chấm online chỉ cần dùng luồng vào/ra chuẩn
---
### 📝 Bài toán

Cho mạng máy tính gồm $N$ máy tính, đánh số từ $1$ đến $N$, và $M$ kết nối (cạnh) giữa chúng. Kết nối giữa máy $U$ và máy $V$ là **hai chiều** (vô hướng).

Yêu cầu: Kiểm tra xem có đường truyền dữ liệu (đường đi) từ máy giáo viên (máy số $1$) đến máy học sinh (máy số $K$) hay không.

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

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

* Dòng 1: Ba số nguyên $N, M, K$.
* $M$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $U, V$ cho biết có đường cáp nối trực tiếp từ máy $U$ đến máy $V$.

Giới hạn:
* $0 < N \le 100$.
* $M$ tối đa là $N(N-1)/2$.
* $1 \le K \le N$.

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

Ghi ra file `NET.out`:

* Ghi ra thông báo `yes` nếu có đường truyền dữ liệu từ máy $1$ đến máy $K$.
* Ghi ra thông báo `no` nếu không có đường truyền dữ liệu.

---
### ✨ Ví dụ

| Input (`NET.inp`) | Output (`NET.out`) |
| :--- | :--- |
| `6 6 3` `1 2` `1 5` `2 5` `3 4` `4 5` `4 6` | `yes` |

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Điểm |
| :--- | :--- | :--- |
| 1 | $N \le 50$ | $50\%$ |
| 2 | $N \le 100$ | $50\%$ |

---

✅ Đã AC: 0 / 0 submissions