Dynamic Connectivity Offline
Xem dạng PDF
Bạn được cho một đồ thị vô hướng rỗng với ~n~ đỉnh. Bạn cần trả lời các truy vấn của ba loại sau:
"~+~ ~u~ ~v~" — thêm một cạnh vô hướng ~u - v~ vào đồ thị.
"~-~ ~u~ ~v~" — xóa một cạnh vô hướng ~u - v~ khỏi đồ thị.
"~?~" — tính số lượng thành phần liên thông trong đồ thị.
Input
Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le n \le 3 \cdot 10^5, 0 \le m \le 3 \cdot 10^5)~ — số lượng đỉnh và số lượng truy vấn.
~m~ dòng tiếp theo mô tả các truy vấn thuộc một trong ba loại sau:
~+~ ~u~ ~v~ ~(1 \le u \neq v \le n)~. Đảm bảo rằng đồ thị không có cạnh ~u - v~ trước đó.
~-~ ~u~ ~v~ ~(1 \le u \neq v \le n)~. Đảm bảo rằng đồ thị có cạnh ~u - v~ trước đó.
~?~
Output
Với mỗi truy vấn ~?~, in ra số lượng thành phần liên thông trong đồ thị tại thời điểm truy vấn đó, mỗi kết quả in ra trên một dòng riêng biệt.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~n, m \le 5000~ |
| 2 | ~70~ | Không có ràng buộc gì thêm |
Sample Input 1
5 11
?
+ 1 2
+ 2 3
+ 3 4
+ 4 5
+ 5 1
?
- 2 3
?
- 4 5
?
Sample Output 1
5
1
1
2
Sample Input 2
11 16
?
+ 2 8
+ 9 10
+ 5 6
+ 4 11
- 4 11
+ 8 11
?
?
- 5 6
- 8 11
- 9 10
+ 6 11
- 2 8
?
+ 10 11
Sample Output 2
11
7
7
10
Notes
Giải thích bộ test đầu tiên:
Ban đầu các thành phần liên thông là (1); (2); (3); (4); (5)
Sau truy vấn thứ hai, các thành phân liên thông là (1, 2); (3); (4); (5)
Sau truy vấn thứ ba, các thành phần liên thông là (1, 2, 3); (4); (5)
~\dots~
Bình luận
Bài tương tự với giới hạn thấp hơn một chút
Bài gần tương tự
i give up :(
Don't give up,try harder