Elearning CodePath – CTP Online Judge

Thành phần Liên thông Lớn nhất

GEN010

🟢 Easy #Graph #BFS/DFS #Connected Components

### 📌 Thông tin chung

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

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

Yêu cầu:
1. Tìm **vùng liên thông** (thành phần liên thông) có số lượng đỉnh **lớn nhất**.
2. **Quy tắc phá vỡ hòa:** Nếu có nhiều vùng liên thông cùng có số lượng đỉnh lớn nhất, chọn vùng liên thông có **thứ tự từ điển nhỏ nhất**. (Thứ tự từ điển được xét trên dãy đỉnh đã được sắp xếp tăng dần).

**Đầu ra yêu cầu:**
1. Số lượng đỉnh của vùng liên thông tìm được.
2. Dãy các đỉnh trong vùng liên thông đó (đã được sắp xếp tăng dần).

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

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

* Dòng 1: Ghi hai số nguyên $N$ và $M$.
* $M$ dòng tiếp theo: Mỗi dòng ghi 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 `MAXDINHLT.OUT` gồm hai dòng:

* Dòng 1: Số lượng đỉnh trong vùng liên thông lớn nhất tìm được.
* Dòng 2: Các đỉnh trong vùng liên thông đó, sắp xếp theo thứ tự tăng dần và cách nhau bởi dấu cách.

---
### 🏷 Phân Subtask

Bài toán này có thể giải bằng thuật toán duyệt đồ thị (DFS hoặc BFS) hoặc Disjoint Set Union (DSU) trong độ phức tạp $O(N+M)$ hoặc gần $O(N \alpha(N))$. Do $N, M$ nhỏ ($3000$), cả hai phương pháp đều chấp nhận được.

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

---

✅ Đã AC: 0 / 0 submissions