Dynamic Connectivity
View as PDFCho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Có ~2~ loại thao tác cần thực hiện:
~1.~ Thêm ~1~ cạnh giữa ~2~ đỉnh ~a~ và ~b~.
~2.~ Xóa ~1~ cạnh giữa ~2~ đỉnh ~a~ và ~b~. Dữ liệu đảm bảo tồn tại cạnh giữa đỉnh ~a~ và ~b~ trước khi xóa.
Nhiệm vụ của bạn là đếm số thành phần liên thông của đồ thị sau mỗi thao tác được thực hiện
Input
Dòng đầu tiên gồm ~3~ số nguyên ~n, m, k~ (~2 \le n \le 10^5, 1 \le m, k \le 10^5~)
~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số ~a, b~ là ~1~ cạnh của đồ thị ban đầu. Có tối đa ~1~ cạnh giữa ~2~ đỉnh bất kì. (~1 \le a, b \le n~)
~k~ dòng tiếp theo, mỗi dòng gồm ~3~ số ~t, a, b~. Khi ~t = 1~ (thêm cạnh) hoặc ~t = 2~ (xóa cạnh). ~1~ cạnh được thêm giữa ~2~ đỉnh khi chưa tồn tại cạnh giữa ~2~ đỉnh đó, và chỉ cạnh đã tồn tại có thể được xóa.
Output
In ra ~k + 1~ số: đầu tiên là số thành phần liên thông trước khi các thao tác diễn ra, và số thành phần liên thông sau mỗi thao tác biến đổi.
Sample Input 1
5 3 3
1 4
2 3
3 5
1 2 5
2 3 5
1 1 2
Sample Output 1
2 2 2 1
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.