Elearning CodePath – CTP Online Judge

Liệt kê thành phần liên thông

GR07_TPLTLIETKE

🟢 Easy

## Đề bài

Cho một đồ thị vô hướng gồm `n` đỉnh và `m` cạnh. Hãy tìm tất cả các thành phần liên thông của đồ thị.

Các thành phần được in theo thứ tự tăng dần của đỉnh nhỏ nhất trong thành phần. Trong mỗi thành phần, các đỉnh cũng được in tăng dần.

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `n, m`.
- `m` dòng tiếp theo, mỗi dòng chứa hai số `u, v`, biểu diễn một cạnh vô hướng.

## Dữ liệu ra

- Dòng đầu in số thành phần liên thông `c`.
- `c` dòng tiếp theo, mỗi dòng in:
  - kích thước của thành phần;
  - sau đó là các đỉnh thuộc thành phần, theo thứ tự tăng dần.

## Ràng buộc

- `1 <= n <= 200000`
- `0 <= m <= 200000`
- Không có cạnh lặp, không có khuyên.

## Subtask

- Subtask 1: `n <= 50`, `m <= 200`.
- Subtask 2: `n <= 5000`, `m <= 20000`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

### Input
```text
9 6
1 2
2 3
4 5
6 7
7 8
8 6
```

### Output
```text
4
3 1 2 3
2 4 5
3 6 7 8
1 9
```

## Giải thích ví dụ

Các đỉnh `1, 2, 3` đi được tới nhau nên thuộc cùng một thành phần. Đỉnh `9` không nối với đỉnh nào nên là một thành phần riêng.

✅ Đã AC: 1 / 1 submissions