Elearning CodePath – CTP Online Judge

Kết nối thành phần

DSU01_CONN

## Đề bài

Có `N` đỉnh được đánh số từ `1` đến `N`. Ban đầu chưa có cạnh nào giữa các đỉnh.

Bạn cần xử lý `Q` thao tác thuộc một trong hai loại:

- `1 u v`: thêm một cạnh nối giữa `u` và `v`.
- `2 u v`: hỏi hiện tại `u` và `v` có nằm trong cùng một thành phần liên thông hay không.

Một cạnh được thêm nhiều lần vẫn được xem như chỉ giúp nối hai thành phần nếu trước đó chúng chưa liên thông.

## Dữ liệu vào

- Dòng đầu gồm hai số nguyên `N Q`.
- `Q` dòng tiếp theo, mỗi dòng có dạng `type u v`.

## Dữ liệu ra

Với mỗi thao tác loại `2`, in ra:

- `YES` nếu `u` và `v` liên thông.
- `NO` nếu ngược lại.

## Ràng buộc

- `1 <= N <= 200000`
- `1 <= Q <= 200000`
- `1 <= u, v <= N`
- `type` thuộc `{1, 2}`
- Có ít nhất một thao tác hỏi.

## Subtask

| Subtask | Điểm | Ràng buộc |
| --- | ---: | --- |
| 1 | 18 | `N, Q <= 20` |
| 2 | 32 | `N, Q <= 1000` |
| 3 | 50 | Không có ràng buộc bổ sung |

## Ví dụ

### Input

```text
5 6
2 1 2
1 1 2
2 1 2
1 3 4
1 2 3
2 1 4
```

### Output

```text
NO
YES
YES
```

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

Ban đầu `1` và `2` chưa liên thông nên câu hỏi đầu tiên trả lời `NO`.

Sau khi thêm cạnh `(1, 2)`, hai đỉnh này liên thông.

Tiếp đó thêm `(3, 4)` rồi `(2, 3)`, khi đó `1, 2, 3, 4` cùng thuộc một thành phần, nên câu hỏi `1 4` trả lời `YES`.

✅ Đã AC: 1 / 1 submissions