Dynamic Connectivity

题目描述

考虑一个无向图，该图由 $n$ 个节点和 $m$ 条边组成。有两种类型的事件可能发生： 你的任务是在每次事件后报告连通分量的数量。

输入格式

第一行输入包含三个整数 $n, m$ 和 $k$：节点数、边数和事件数。 接下来有 $m$ 行描述这些边。每行有两个整数 $a$ 和 $b$：表示节点 $a$ 与节点 $b$ 之间有一条边。任意一对节点之间最多有一条边。 然后有 $k$ 行描述事件。每行为形式 "$t a b"，其中$t$ 为 $1$（新建一条边）或 $2$（移除一条边）。新建的边总是在两个之间原本没有边的节点间创建，且只有存在的边才能被移除。

输出格式

输出 $k+1$ 个整数：首先输出在第一个事件发生前的连通分量数量，随后在每次事件后输出新的连通分量数量。

5 3 3
1 4
2 3
3 5
1 2 5
2 3 5
1 1 2

2 2 2 1

提示

$2 \le n \le 10^5$ $1 \le m,k \le 10^5$ $1 \le a,b \le n$

标签: CSES2133|先进技术

来源

CSES2133|先进技术