一、什么是并查集
并查集的逻辑结构是一个包含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]; //返回父节点}}
