Elearning CodePath – CTP Online Judge

Ma trận kề có hướng sang danh sách cung

GR02_CUNGBAC

🟢 Easy

## Đề bài

Cho một đồ thị có hướng đơn gồm `n` đỉnh, được biểu diễn bằng ma trận kề `A`.

Nếu `A[i][j] = 1` thì có cung đi từ `i` đến `j`. Hãy in ra danh sách các cung theo thứ tự tăng dần của đỉnh đầu, nếu cùng đỉnh đầu thì tăng dần theo đỉnh cuối. Đồng thời, hãy in bán bậc ra và bán bậc vào của từng đỉnh.

## Dữ liệu vào

- Dòng đầu chứa số nguyên `n`.
- `n` dòng tiếp theo, mỗi dòng chứa `n` số `0` hoặc `1`, là ma trận kề của đồ thị có hướng.

## Dữ liệu ra

- Dòng đầu in số cung `m`.
- `m` dòng tiếp theo, mỗi dòng in một cung `u v`.
- Dòng tiếp theo in `OUT d1 d2 ... dn`, trong đó `di` là bán bậc ra của đỉnh `i`.
- Dòng cuối in `IN d1 d2 ... dn`, trong đó `di` là bán bậc vào của đỉnh `i`.

## Ràng buộc

- `1 <= n <= 250`
- `A[i][j]` chỉ bằng `0` hoặc `1`
- `A[i][i] = 0`

## Subtask

- Subtask 1: `n <= 8`.
- Subtask 2: `n <= 60`.
- Subtask 3: Không có ràng buộc bổ sung.

## Ví dụ

### Input
```text
4
0 1 0 1
0 0 1 0
1 0 0 0
0 0 1 0
```

### Output
```text
5
1 2
1 4
2 3
3 1
4 3
OUT 2 1 1 1
IN 1 1 2 1
```

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

Đỉnh `1` có hai cung đi ra là `1 -> 2` và `1 -> 4`, nên bán bậc ra của đỉnh `1` bằng `2`.
Đỉnh `3` nhận hai cung từ `2` và `4`, nên bán bậc vào của đỉnh `3` bằng `2`.

✅ Đã AC: 1 / 2 submissions