499. 合并集合
时间限制：1000 MS 内存限制：64 MB
题目描述
# 合并集合 ## 题目描述 一共有 $n$ 个数，编号为 $1 \sim n$。最开始，每个数各自在一个集合中。 现在要依次进行 $m$ 个操作，操作共有两种： - `M a b`：将编号为 $a$ 和 $b$ 的两个数所在的集合合并。如果这两个数已经在同一个集合中，则忽略这个操作。 - `Q a b`：询问编号为 $a$ 和 $b$ 的两个数是否在同一个集合中。 请输出每次询问的结果。 ## 输入格式 从文件 `unionfind.in` 读入数据。 第一行包含两个整数 $n$ 和 $m$，分别表示数的个数和操作的个数。 接下来 $m$ 行，每行包含一个操作，格式为 `M a b` 或 `Q a b`。 ## 输出格式 将结果输出到文件 `unionfind.out`。 对于每个 `Q a b` 操作，如果 $a$ 和 $b$ 在同一个集合中，输出 `Yes`；否则输出 `No`。 按询问出现的顺序输出，每个结果占一行。如果没有询问操作，则不输出任何内容。 ## 数据范围 对于所有测试数据： - $1 \le n,m \le 10^5$； - $1 \le a,b \le n$。 ## 样例输入 ``` 4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4 ``` ## 样例输出 ``` Yes No Yes ``` ## 运行限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。