Elearning CodePath – CTP Online Judge

Xây Dựng Đường

BUILDROAD

🟢 Hard #Graph #BFS/DFS

### 📌 Thông tin chung

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

Quốc gia $X$ có $N$ thành phố và $M$ con đường nối giữa chúng.
Yêu cầu:
1.  Xây dựng thêm một số con đường mới sao cho luôn có đường đi giữa **mọi cặp thành phố**.
2.  Tìm ra số lượng tối thiểu $K$ các con đường cần thiết.
3.  Xác định các con đường cần được xây dựng.

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

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

* Dòng đầu tiên: Chứa hai số nguyên $N$ và $M$: số lượng thành phố và con đường.
* $M$ dòng tiếp theo: Mỗi dòng mô tả một con đường, chứa hai số nguyên $a$ và $b$: có một con đường nối giữa hai thành phố $a$ và $b$.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le M \le 2 \cdot 10^5$.
* $1 \le a, b \le N$.
* Một con đường luôn nối hai thành phố khác nhau, và có tối đa một con đường giữa hai thành phố bất kỳ.

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

Ghi ra file `BUILDROAD.OUT`:

* Dòng đầu tiên: In ra một số nguyên $K$: số lượng con đường cần xây thêm.
* $K$ dòng sau đó: Mỗi dòng mô tả một con đường mới.
    * Nếu có nhiều giải pháp, in ra giải pháp mà chỉ số thành phố được đưa ra theo thứ tự **tăng dần** trên mỗi dòng (ví dụ: in `1 5` thay vì `5 1`).

---
### ✨ Ví dụ

| Input (`BUILDROAD.INP`) | Output (`BUILDROAD.OUT`) |
| :--- | :--- |
| `4 2` <br> `1 3` <br> `2 4` | `1` <br> `2 3` |

Giải thích:
$N=4, M=2$. Các đường đã có: $(1, 3), (2, 4)$.
Đồ thị có 2 thành phần liên thông (TPLT): $C_1 = \{1, 3\}$ và $C_2 = \{2, 4\}$.
Cần xây thêm $2 - 1 = 1$ con đường để liên thông hóa.
Chọn đường nối 1 thành phố ở $C_1$ và 1 thành phố ở $C_2$. Ví dụ: $(1, 2), (1, 4), (3, 2), (3, 4)$.
Chọn $(2, 3)$ vì $2 < 3$.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $90\%$ |
| 2 | $N \le 10^5$ | $10\%$ |

---

✅ Đã AC: 3 / 13 submissions