Elearning CodePath – CTP Online Judge

Làm sạch danh sách kề

GR03_LAMDEPDSK

🟢 Easy

## Đề bài

Một đồ thị vô hướng đơn được ghi lại dưới dạng danh sách kề, nhưng dữ liệu có thể bị thừa:

- Một cạnh có thể xuất hiện nhiều lần.
- Có thể chỉ xuất hiện ở một phía, ví dụ dòng của `u` có `v` nhưng dòng của `v` không có `u`.
- Có thể có khuyên `u u`, cần bỏ qua.

Hãy chuyển dữ liệu đó thành danh sách kề chuẩn của đồ thị vô hướng đơn.

## Dữ liệu vào

- Dòng đầu chứa số nguyên `n`.
- Với mỗi đỉnh `i` từ `1` đến `n`, có một dòng gồm:
  - số nguyên `k_i`;
  - tiếp theo là `k_i` số nguyên, là các đỉnh được ghi trong danh sách của `i`.

## Dữ liệu ra

- Dòng đầu in số cạnh phân biệt `m` sau khi làm sạch.
- `n` dòng tiếp theo, dòng thứ `i` có dạng:

```text
i: danh_sach_dinh_ke
```

Các đỉnh kề phải được in tăng dần. Nếu đỉnh `i` không có đỉnh kề nào thì chỉ in `i:`.

## Ràng buộc

- `1 <= n <= 200000`
- `0 <= tổng k_i <= 300000`
- `1 <= v <= n` với mọi số được liệt kê.

## Subtask

- Subtask 1: `n <= 8`, `tổng k_i <= 30`.
- Subtask 2: `n <= 5000`, `tổng k_i <= 20000`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

### Input
```text
5
4 2 2 1 3
2 1 3
3 1 4 4
1 3
2 5 5
```

### Output
```text
4
1: 2 3
2: 1 3
3: 1 2 4
4: 3
5:
```

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

Các mục `1 1`, `5 5` là khuyên nên bị bỏ. Các cạnh lặp như `1 2` chỉ được tính một lần.

✅ Đã AC: 1 / 2 submissions