目录
学习了二叉树和并查集，并进行了整理后，做了几个题练手
P3367 【模板】并查集
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N,MN,M ,表示共有 NN 个元素和 MM 个操作。
接下来 MM 行，每行包含三个整数 Z_i,X_i,Y_iZi,Xi,Yi 。
当 Z_i=1Zi=1 时，将 X_iXi 与 Y_iYi 所在的集合合并。
当 Z_i=2Zi=2 时，输出 X_iXi 与 Y_iYi 是否在同一集合内，是的输出 Y ；否则输出 N 。
输出格式
对于每一个 Z_i=2Zi=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
说明/提示
对于 30\%30% 的数据，N \le 10N≤10，M \le 20M≤20。
对于 70\%70% 的数据，N \le 100N≤100，M \le 10^3M≤103。
对于 100\%100% 的数据，1\le N \le 10^41≤N≤104，1\le M \le 2\times 10^51≤M≤2×105，1 \le X_i, Y_i \le N1≤Xi,Yi≤N，Z_i \in \{ 1, 2 \}Zi∈{1,2}。
思路
1、初始化祖先为自己
2、假如z==1，进行合并操作（合并操作就是把一个节点的祖先变为另一个节点的祖先。）
3、假如z==2，进行查找x,y的祖先，如果相等输出Y，反之输出N（查找操作就是不断地向上走，直到找到祖先为止）
4、注意压缩路径
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[10010];
int z,x,y;
int find(int i)
{
if(fa[i]==i)
return i;//递归出口
else
{
fa[i]=find(fa[i]);//路径压缩
return fa[i];
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
while(m--)
{
cin>>z>>x>>y;
if(z==1)
fa[find(x)]=find(y);
else
{
if(find(x)==find(y))
printf("Y\n");
else
printf("N\n");
}
}
}P1551 亲戚
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：xx 和 yy 是亲戚，yy 和 zz 是亲戚，那么 xx 和 zz 也是亲戚。如果 xx，yy 是亲戚，那么 xx 的亲戚都是 yy 的亲戚，yy 的亲戚也都是 xx 的亲戚。
输入格式
第一行：三个整数 n,m,pn,m,p，（n,m,p \le 5000n,m,p≤5000），分别表示有 nn 个人，mm 个亲戚关系，询问 pp 对亲戚关系。
以下 mm 行：每行两个数 M_iMi，M_jMj，1 \le M_i,~M_j\le N1≤Mi, Mj≤N，表示 M_iMi 和 M_jMj 具有亲戚关系。
接下来 pp 行：每行两个数 P_i,P_jPi,Pj，询问 P_iPi 和 P_jPj 是否具有亲戚关系。
输出格式
pp 行，每行一个 Yes 或 No。表示第 ii 个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
输入 #1复制
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6
输出 #1复制
Yes Yes No
思路
1、前m组数进行合并操作
2、后p组数进行查找操作
代码实现
#include<bits/stdc++.h>
using namespace std;
int n,m,p,fa[10010];
int z,x,y;
int find(int i)
{
if(fa[i]==i)
return i;//递归出口
else
{
fa[i]=find(fa[i]);//路径压缩
return fa[i];
}
}
int main()
{
cin>>n>>m>>p;
for(int i=1;i<=n;i++)
fa[i]=i;
while(m--)
{
cin>>x>>y;
fa[find(x)]=find(y);
}
while(p--)
{
cin>>x>>y;
if(find(x)==find(y))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}