【问题描述】

　　n 个不同元素分布在若干个互不相交的集合中，需要进行以下 3 个操作：

　　1.合并两个集合（Merge）。
　　2.查询元素所在的集合（Find）。
　　3.查询两个元素是否属于同一个集合（Judge）。

　　请你设计一种数据结构，支持上面三种操作，并且时间效率尽量的高。

【输入格式】

　　第 1 行一个整数 n，表示有 nn 个不同元素组成的 n 个集合：{1}、{2}、…、{n}1、2、…、n。
　　第 2 行一个整数 m，表示有 m 个操作。
　　接下来的 m 行，每行一个操作，格式如下：
　　　Merge x y：表示合并 x 和 y 所在的两个集合，如果他们已经在同一个集合，则忽略这个操作。
　　　Judge x y：表示查询 x 和 y 是否在同一个集合中，如果在同一个集合，就输出Yes，否则输出No。
　　以上操作中的 x,y 均满足 1≤x,y≤n。

【输出格式】

　　输出每个 Judge 的结果。

【输入输出样例1】

　Input

6
10
Merge 1 2
Judge 1 3
Judge 1 2
Merge 2 5
Merge 3 6
Judge 1 5
Judge 3 2
Merge 2 6
Judge 1 5
Judge 4 5

　Output

No
Yes
Yes
No
Yes
No

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 const int maxn=0x3f3f3f;
 5 int pa[maxn];
 6 void makeset()
 7 {
 8     for(int i=1;i<=n;i++)
 9     {
10         pa[i]=i;
11     }
12 }
13 int Find(int x)
14 {
15     int r=x;
16     while(pa[r]!=r) 
17     r=pa[r];
18     
19     while(x!=r)
20     { 
21     int y=pa[x];
22     pa[x]=r;
23     x=y;
24     }
25     return r;
26 }
27 void Merge(int x,int y)
28 {
29     pa[Find(x)]=Find(y); 
30 }
31 bool Judge(int x,int y)
32 {
33     return Find(x)==Find(y);
34 }
35 int main()
36 {
37     scanf("%d%d",&n,&m);
38     makeset();
39     string s;
40     while(m--)
41     {
42         cin>>s;
43         if(s=="Merge")
44         {
45             int x,y;
46             scanf("%d%d",&x,&y);
47             Merge(x,y);
48         }
49         if(s=="Judge")
50         {
51             int x,y;
52             scanf("%d%d",&x,&y);
53             if(Judge(x,y)==1)
54             printf("Yes\n");
55             else
56             printf("No\n");
57         }
58     }
59     return 0;
60 }