6967. 动态连通性 (Dynamic Connectivity)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 考虑一个由 $n$ 个节点和 $m$ 条边组成的无向图。在这个图上可能会发生两类事件： 1. 在节点 $a$ 和 $b$ 之间创建一条新边。 2. 移除节点 $a$ 和 $b$ 之间已存在的一条边。 你的任务是在初始状态下以及每次事件发生后，报告当前图中的连通分量个数。 ## 输入格式 第一行包含三个整数 $n, m$ 和 $k$，分别表示节点数、初始边数以及事件次数。 接下来 $m$ 行描述初始的边。每行包含两个整数 $a$ 和 $b$，表示这两个节点之间有一条无向边。任意两点间最多只有一条直接相连的边。 接下来 $k$ 行描述发生的事件。每行的格式为 `t a b`，其中： * $t = 1$：在 $a$ 和 $b$ 之间创建一条新边。 * $t = 2$：移除 $a$ 和 $b$ 之间已有的边。 新边始终在当前没有边直接相连的两个节点之间创建，且只有当前已存在的边才会被移除。 ## 输出格式 输出 $k+1$ 个整数，依次表示初始状态（第一个事件之前）以及每次事件发生后，图中的连通分量个数。 ## 输入输出样例 ### 输入 #1 ``` 5 3 3 1 4 2 3 3 5 1 2 5 2 3 5 1 1 2 ``` ### 输出 #1 ``` 2 2 2 1 ``` ## 说明/提示 ### 数据规模与约定 * $2 \le n \le 10^5$ * $1 \le m, k \le 10^5$ * $1 \le a, b \le n$