知识点：并查集+路径压缩
一共有n个数，编号是1~n，最开始每个数各自在一个集合中。
现在要进行m个操作，操作共有两种：
- “M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
- “Q a b”，询问编号为a和b的两个数是否在同一个集合中；
输入格式
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
import java.io.*;
import java.lang.Integer;class Main{static int N = 100010;static int[] p = new int[N];static int find(int x){//查找根节点 + 路径压缩if(p[x] != x)p[x] = find(p[x]);return p[x];}public static void main(String[] args)throws Exception{BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter buw = new BufferedWriter(new OutputStreamWriter(System.out));String[] params = buf.readLine().split(" ");int n = Integer.valueOf(params[0]);int m = Integer.valueOf(params[1]);for(int i = 1; i <= n; ++i){p[i] = i;}for(int i = 0; i < m; ++i){String[] info = buf.readLine().split(" ");int a = Integer.valueOf(info[1]);int b = Integer.valueOf(info[2]);if("M".equals(info[0])){p[find(a)] = find(b);//将a集合并入b集合}else{if(find(a) != find(b))buw.write("No\n");else buw.write("Yes\n");}}buw.flush();buf.close();buw.close();}
}