【前言】
并查集（Disjoint Set）是一种常见的数据结构，用于处理不相交集合的合并与查询问题。在C++中，可以通过实现一个并查集类来使用并查集的功能。
【引入】
题目：朋友圈
假设有n个人，编号为1到n。开始时，每个人的朋友圈中只有自己。
然后，给出m对朋友关系，表示两个人是朋友关系。例如，(1, 2)表示人1和人2是朋友，(2, 3)表示人2和人3是朋友。现在需要回答一些查询，每个查询给出两个人的编号，要求判断他们是否属于同一个朋友圈。
我们可以把每个人看成一个节点，一个朋友圈看成一棵树。一开始每个人都是一个独立节点（也就是一片森林），如果有两人是朋友关系那么把两个节点合并（也就是一棵树）。询问是不是朋友关系要判断两人的节点有没有合并过（也就是是否在同一棵树上）。
1 2 3 图1（三人不存在任何朋友关系）
1——2 3 图2（1和2是朋友关系）
1——2——3 图3（2和3是朋友关系，1、2、3都是朋友关系）
【初始化】
定义一个father[]数组用来表示各个节点的父节点，节点如果是独立的话那就父节点是自己本身。因为一开始大家没有任何朋友关系，所以n个节点都是独立的。
for(int i=1;i<=n;i++)father[i]=i;【找根（find）】
既然朋友圈是一棵树，就要想办法查询树的根节点（合并、判断等操作都需要找根）。用递归就可以了。
int find(int x)
{
if(x==father[x]）return x;//边界条件，x的父节点指向自己说明是根节点。
return find(father[x]);
}如果频繁调用就有可能TLE（超时），所以father[]数组直接表示各个节点的根节点（路径压缩，时间复杂度是O(1)）。
写法一：
int find(int x)
{
if(x!=father[x])father[x]=find(father[x]);
return father[x];
}写法二：
int find(int x)
{
if(x==father[x])return x;
father[x]=find(father[x]);
return father[x];
}【合并（union）】
要如何然两个节点合并形成一个朋友圈（树）呢？1和2有朋友关系我们把2的根节点指向1的根节点就可以表示两人在的两个朋友圈合并为一个朋友圈。
void unionn(int x,int y)
{
x=find(x);
y=find(y);
father[y]=x;
}【判断（judge）】
判断是否有朋友关系只要判断是否在同一朋友圈就可以了，即根节点是否相同。
bool judge(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)return 0;
return 1;
}【结尾】
不多说给上文章【引入】部分题目的代码。
#include<bits/stdc++.h>
using namespace std;
int n,m,q,father[100000];
int find(int x)
{
if(x!=father[x])father[x]=find(father[x]);
return father[x];
}
void unionn(int x,int y)
{
x=find(x);
y=find(y);
father[y]=x;
}
bool judge(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y)return 0;
return 1;
}
int main(){
int x,y;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++){
cin>>x>>y;
unionn(x,y);
}
for(int i=1;i<=q;i++){
cin>>x>>y;
if(judge(x,y))cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;
}
