Dynamic Connectivity

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho 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

Please read the guidelines before commenting.



  • -28
    themluachon2008  commented on Dec. 28, 2023, 2:06 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -59
    Loc2008  commented on Dec. 27, 2023, 8:13 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -15
    ngthang2022  commented on Dec. 21, 2023, 3:34 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.