Dynamic Connectivity
Xem dạng 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
Bình luận
Bài tương tự với giới hạn cao hơn một chút
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.