并查集
介绍
- 实现集合的合并和查找
- 用树来存储一个集合
- 如果两个点有共同根，就在一个集合里
- 合并只需要把一个点的根放到另一个点的根的下面就行
两种优化
按秩合并
- 把矮的集合的根放到高的集合的根的下面
- 总能保证深度不超过logn
路径压缩（简单常用）
- 操作复杂度O(logn)
- 忽视两个点的父子关系，只关心在哪个集合里
- 在对一个点找根的时候同时将他的父亲变为根
int father[202020];//存储每个节点的父节点编号
int find(int x){
return father[x]==x?x:father[x]=find(father[x])；
}
void merge(int x,int y){
fa[find(x)]=find(y);//x的根接到y的根的下面
}
美团公司福利 3017人发布