算法笔记：并查集

一、什么是并查集

并查集的逻辑结构是一个包含N个元素的集合，如图：

我们将各个元素划分为若干个互不相交的子集，如图：

二、并查集的基本操作

（一）初始化

初始化可以先将每个子集指向自己

 //初始化int [] un=new int[10];for (int i = 0; i < un.length; i++) { //先使得每个子集指向子集un[i]=i;}

（二）Find操作

返回指定索引的根

//并查集查询public int find(int x){if (un[x]==x){  //如果当前并查集指向自己 那么直接返回当前值即可return x;}else { //如果不指向自己 则代表有可能有指向链 那么就递归寻找  直到找到最终的根节点return find(un[x]);}}

（三）Union操作
●合并操作即将一个根指向另一个指定节点
 

//合并 也就是使得i指向jpublic void merge(int i,int j){un[find(i)]=find(j);  // un[find(i)] 是指 如果i索引 有指向其他节点的话 那么肯定要遍历到最终指向的父节点 然后将父节点与指定索引值合并 没有指向的话那么就是直接使得当前位置i指向j}

（四）Union操作（路径压缩）

 //合并（压缩路径）public int union(int x){if (un[x]==x){ //代表此时已经是跟节点return x;}else {un[x]=union(un[x]); //使得每一个节点都指向该父节点 比如1—>2—>3   3是最终根节点 那么这样写的最终效果就是  1->3  2—>3  3->3return un[x]; //返回父节点}}