【算法】无趣的并查集

并查集

---

定义

把许多有关系的人合并成一个集合 然后询问其中的人是否有关系的时候用并查集

---

思路

用树存图 每一次输入判断他们的祖先是否同一个 不同的话就把两个数的祖先改成同一个 最后的询问只要O（1）

---

例子和代码

一个入门的并查集题目

洛谷P1551:https://www.luogu.org/problemnew/show/P1551

代码：

#include<iostream> 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"<<endl;//是 } else cout<<"No"<<endl;//否 } }

转载于:https://www.cnblogs.com/BrokenString/p/9279516.html