并查集

---

定义

把许多有关系的人合并成一个集合

然后询问其中的人是否有关系的时候用并查集

---

思路

用树存图

每一次输入判断他们的祖先是否同一个

不同的话就把两个数的祖先改成同一个

最后的询问只要O（1）

---

例子和代码

一个入门的并查集题目

洛谷P1551:

代码：

#include
    
     using namespace std;int father[5001];int n,m,p;int find(int x){    if(father[x]!=x)//路径压缩优化    father[x]=find(father[x]);//把路上的所有点祖先全部改掉    return father[x];}void unionn(int x,int y){    father[y]=x;//y的祖先为x的祖先                //相当于合并祖先}int main(){    cin>>n>>m>>p;    for(int i=1;i<=n;i++)    {        father[i]=i;//所有数据初始祖先为自己                    //独立的一个数为一个集合    }    for(int i=1;i<=m;i++)    {        int x,y;        cin>>x>>y;        int r1,r2;        r1=find(x);        r2=find(y);//寻找两个数的祖先        if(r1!=r2)//如果不是同一个祖先        {            unionn(r1,r2);//合并        }    }    for(int i=1;i<=p;i++)    {        int x,y;        cin>>x>>y;        if(find(x)==find(y))//如果是同一个祖先        {            cout<<"Yes"<