CSES2133 动态连通性
#CS2133. 动态连通性
动态连通性
题目背景
翻译自 CSES-2133 题。
题目描述
考虑一个由n个节点和m条边组成的无向图。可能会发生两种类型的事件：
-
在节点a和节点b之间创建一条新的边。
-
移除节点a和节点b之间的一条已存在的边。
你的任务是报告每次事件之后的连通分量数量。
输入格式
第一行包含三个整数n、m和k：分别表示节点数、边数和事件数。
接下来有m行描述图中的边。每行包含两个整数a和b，表示节点a和节点b之间有一条边。图中每一对节点之间最多只有一条边。
然后有k行描述事件。每行的格式为“t a b”，其中t是1（表示创建一条新边）或2（表示移除一条边）。新边总是创建在两个节点之间，这两个节点之间原本没有边，且只有已存在的边可以被移除。
输出格式
输出k+1k+1k+1个整数：首先输出事件发生前的连通分量数量，然后输出每次事件发生后的连通分量数量。
样例
5 3 3
1 4
2 3
3 5
1 2 5
2 3 5
1 1 2
2 2 2 1
说明/提示