Kết Nối Động
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Python 3
5.0s
Giới hạn bộ nhớ:
256M
Đầu vào:
stdin
Đầu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Java, Kotlin, Pascal, Python, Scratch
Cho một đồ thị vô hướng có đỉnh với cạnh ban đầu. Sau đó có thao tác, mỗi thao tác là một trong hai loại:
- Thêm cạnh: Thêm cạnh vào đồ thị.
- Xóa cạnh: Xóa cạnh khỏi đồ thị.
Sau mỗi trạng thái (trạng thái ban đầu và sau mỗi thao tác), hãy in số thành phần liên thông của đồ thị.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên , , — số đỉnh, số cạnh ban đầu, và số thao tác.
dòng tiếp theo, mỗi dòng chứa hai số nguyên , — mô tả một cạnh ban đầu.
dòng tiếp theo, mỗi dòng mô tả một thao tác:
1 u v— thêm cạnh .2 u v— xóa cạnh (đảm bảo cạnh này đang tồn tại trong đồ thị).
Dữ liệu ra
In số nguyên trên một dòng, cách nhau bởi dấu cách: số thành phần liên thông sau trạng thái ban đầu và sau mỗi thao tác.
Ràng buộc
- ,
- Có thể có nhiều cạnh song song (multi-edge) tại một thời điểm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 3 1 1 2 1 2 3 2 1 2 |
3 2 1 2 | Ban đầu không có cạnh: 3 thành phần. Thêm (1,2): {1,2}, {3} → 2 thành phần. Thêm (2,3): {1,2,3} → 1 thành phần. Xóa (1,2): {1}, {2,3} → 2 thành phần. |
| 4 2 3 1 2 3 4 2 1 2 1 2 3 1 1 4 |
2 3 2 1 | Ban đầu có cạnh (1,2),(3,4): {1,2},{3,4} → 2 thành phần. Xóa (1,2): {1},{2},{3,4} → 3 thành phần. Thêm (2,3): {1},{2,3,4} → 2 thành phần. Thêm (1,4): {1,2,3,4} → 1 thành phần. |
Ghi chú
Đồ thị có thể có nhiều cạnh song song giữa cùng hai đỉnh. Khi xóa cạnh, chỉ xóa một bản sao.
Bình luận