/ Vijos / 题库 /

图的动态连通性

图的动态连通性

时间限制: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

信息

ID
1543
难度
(无)
分类
数据结构 | 并查集图结构 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
4
上传者