Elearning CodePath – CTP Online Judge

Đếm Thành phần Liên thông

GEN008

🟢 Hard #BFS/DFS #Connected Components

### 📌 Thông tin chung

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

Cho đồ thị vô hướng $G=(V, E)$ gồm $N$ đỉnh và $M$ cạnh.

Yêu cầu: Đếm số lượng **vùng liên thông (thành phần liên thông)** của đồ thị.

Một thành phần liên thông là một tập hợp các đỉnh con lớn nhất sao cho giữa hai đỉnh bất kỳ trong tập hợp đều có đường đi.

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

Dữ liệu vào từ file `TPLT.INP`:

* Dòng 1: Ghi hai số nguyên $N$ và $M$.
* $M$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên dương $U, V$ thể hiện có một cạnh vô hướng giữa đỉnh $U$ và $V$.

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

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

Ghi ra file `TPLT.OUT` một số nguyên duy nhất là số lượng vùng liên thông của đồ thị.

---
### ✨ Ví dụ

| Input (`TPLT.INP`) | Output (`TPLT.OUT`) |
| :--- | :--- |
| `9 8` `1 2` `2 3` `2 4` `3 6` `3 7` `6 7` `5 8` `8 9` | `2` |

Giải thích:
* Vùng 1: $\{1, 2, 3, 4, 6, 7\}$
* Vùng 2: $\{5, 8, 9\}$
* Tổng số vùng liên thông là 2.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Điểm |
| :--- | :--- | :--- |
| 1 | $N, M \le 500$ | $40\%$ |
| 2 | $N, M \le 3000$ | $60\%$ |

---

✅ Đã AC: 3 / 13 submissions