图的动态连通性
时间限制:1秒 内存限制:256M
【问题描述】
给出含 \(n\) 个点、\(m\) 条边的无向图,结点编号为 \(1..n\)。现在有 4 类操作:
1、Link \(u\ v\):在结点 \(u\) 和 \(v\) 之间连一条无向边。
2、Query \(u\ v\):查询 \(u\) 和 \(v\) 是否属于同一连通分量。
3、Count 询问当前图的连通分量数。
4、Max 询问当前最大的连同分量。
【输入格式】
第一行:三个整数 \(n,m\),\(n,m\) 的意义如题目描述。
接下来 \(m\) 行:每行两个数 \(u,v\)(\(1≤u,v≤n\)),表示结点 \(u\) 和 \(v\) 之间有条无向边。
接着的一行是一个整数 \(q\),表示操作数。
再接下来 \(q\) 行:每行是题目描述中的四种操作之一。
【输出格式】
输出每个查询的结果,对于Query \(u\ v\) 查询,如果 \(u\) 和 \(v\) 在同一连同分量中输出 yEs,否则输出 nO。
【输入输出样例1】
Input
8 4
8 2
3 7
1 5
6 3
14
Count
Max
Link 3 2
Count
Max
Query 1 2
Link 6 8
Query 2 6
Count
Max
Link 1 3
Query 5 7
Count
Max
Output
4
3
3
5
nO
yEs
3
5
yEs
2
7
【数据说明】
对于 \(100\%\) 的数据,\(0<n,m,q≤200000\)。
【来源】
Mr.he