Elearning CodePath – CTP Online Judge

Xóa đường hỏi kết nối

DSU06_OFFLINE_DEL

🟢 Easy #DSU

## Đề bài

Có `N` thành phố và `M` con đường hai chiều ban đầu. Các con đường được đánh số từ `1` đến `M` theo thứ tự nhập vào.

Bạn cần xử lý `Q` thao tác:

- `1 id`: xóa con đường có mã `id`.
- `2 u v`: hỏi hiện tại có đường đi từ `u` đến `v` hay không.

Mỗi con đường bị xóa nhiều nhất một lần. Các thao tác được thực hiện theo đúng thứ tự trong input.

## Dữ liệu vào

- Dòng đầu gồm ba số nguyên `N M Q`.
- `M` dòng tiếp theo, dòng thứ `id` gồm hai số `u v`, mô tả con đường `id`.
- `Q` dòng tiếp theo mô tả thao tác.

## 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 tại thời điểm đó.
- `NO` nếu ngược lại.

## Ràng buộc

- `1 <= N <= 200000`
- `0 <= M <= 200000`
- `1 <= Q <= 200000`
- `1 <= u, v <= N`
- `1 <= id <= M`
- Mỗi `id` xuất hiện trong thao tác xóa không quá một lần.
- Có ít nhất một thao tác hỏi.

## Subtask

| Subtask | Điểm | Ràng buộc |
| --- | ---: | --- |
| 1 | 20 | `N, M, Q <= 30` |
| 2 | 35 | `N, M, Q <= 5000` |
| 3 | 45 | Không có ràng buộc bổ sung |

## Ví dụ

### Input

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

### Output

```text
YES
NO
NO
```

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

Ban đầu các thành phố `1,2,3,4` tạo thành một đường thẳng nên `1` đi được đến `4`.

Sau khi xóa đường `2` nối `2-3`, đồ thị bị tách thành `{1,2}` và `{3,4}`, nên `1` không còn đi được đến `4`.

Xóa thêm đường `1` không làm `1` nối lại được với `4`.

✅ Đã AC: 1 / 2 submissions