Responsive image

问题 2342 --连通块中点的数量

2342: 连通块中点的数量

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 82
[提交][状态][讨论版][命题人:]

题目描述

给定一个包含 n 个点（编号为 1~n ）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
  1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
  2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
  3. Q2 a，询问点 a 所在连通块中点的数量。

数据范围

1 <= n,m <= 1e5

输入描述

第一行输入一个整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b ，Q1 a b 或 Q2 a 中的一种。

输出描述

对于每个询问命令 Q1 a b，如果 a 和 b 在同一连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点数量。
每个结果占一行。

样例输入

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

样例输出

Yes
2
3

来源

20王代泽 并查集 

[提交][状态]
ACM算法攻关部