介绍

  • 实现集合的合并和查找
  • 用树来存储一个集合
  • 如果两个点有共同根，就在一个集合里
  • 合并只需要把一个点的根放到另一个点的根的下面就行

两种优化

按秩合并

  • 把矮的集合的根放到高的集合的根的下面
  • 总能保证深度不超过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的根的下面
}