By Stockholm
并查集（Union-Find Set）模板
题目描述 如题，现在有一个并查集，你需要完成合并和查询操作。 输入输出格式 输入格式： 第一行包含两个整数 N、M，表示共有 N 个元素和 M 个操作。 接下来 M 行，每行包含三个整数 Zi、Xi、Yi 当 Zi=1 时，将 Xi 与 Yi 所在的集合合并 当 Zi=2 时，输出 Xi 与 Yi 是否在同一集合内，是的话输出 Y；否则 话输出 N 输出格式： 如上，对于每一个 Zi=2 的操作，都有一行输出，每行包含一个大写 字母，为 Y 或者 N 输入输出样例输入样例#1： 4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4 输出样例#1： N Y N Y 说明 时空限制：1000ms,128M 数据规模： 对于 30%的数据，N<=10，M<=20；对于 70%的数据，N<=100，M<=1000； 对于 100%的数据，N<=10000，M<=200000。
思路
思路是这样的，需要将每一个点对其列出一个祖先数组，初始化任何 一个节点都为本节点的祖先节点，然后在合并集合时，注意进行路径 压缩，边寻找边压缩路径，以便下一次的判断。操作 2 就简单一些， 只需要两个节点在更新寻找节点的同时进行对比并更新即可。
代码（C++）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int i,j,n,m,t;
int b[
10001];
int r()
{
int aans=
0;
char ch=getchar();
while(ch<
'0'||ch>
'9')
ch=getchar();
while(ch>=
'0'&&ch<=
'9')
{
aans*=
10;
aans+=ch-
'0';
ch=getchar();
}
return aans;
}
int update(
int xx)
{
return xx==b[xx]?xx:b[xx]=update(b[xx]);
}
int main()
{
n=r(),m=r();
int x,y,z;
for(i=
1;i<=n;i++)b[i]=i;
for(i=
1;i<=m;i++)
{
z=r(),x=r(),y=r();
if(z==
1)
{
b[update(x)]=update(y);
}
if(z==
2)
{
if(update(x)==update(y))
cout<<
"Y"<<endl;
else
cout<<
"N"<<endl;
}
}
return 0;
}
