一、普通版本

并查集是为了解决连接问题的。在很复杂的情况下，哪些元素是相互连接的，值得研究。

并查集的连接，大体可分为两个动作

union(p,q) 连接两个元素 find(p) 查询元素的id

和一个回答。

isConnected(p,q) p和q是否相连

数组表示

ele : 1 2 3 4 5 6 7 8 9 id : 1 1 1 1 1 0 0 0 0

只要id相等，就是相连。

代码如下：

public class UnionFind { private int[] id; private int count; public UnionFind(int n){ count = n; id = new int[n]; for(int i=0;i<n;i++){ id[i] = i; } } // 查询元素p的id int find(int p){ assert (p>=0 && p<count); return id[p]; } // 两个元素如果id相等，即为相连 boolean isConnected(int p,int q){ return find(p)==find(q); } // 连接两个元素 void union(int p,int q){ int pId = find(p); int qId = find(q); // 判断是否相连 if(pId==qId){ return; } // 将所有与p元素相连的元素（包括自己），都改为与q元素相连。 for(int i=0;i<count;i++){ if(id[i]==pId){ id[i]=qId; } } } }

二、改进union的遍历

第一种思路清晰，用id号表示是否相连，id相等即为相连。 下面换个思路 1、将一个元素看成一个节点 2、如果想让5与2相连 3、想让7与3相连 4、 因为7的根是5，3的根是2，所以只要5和2相连，自然7和3相连。

数据结构：

ele: 0 1 2 3 4 5 6 7 8 9 parent : 0 1 2 3 4 5 6 7 8 9

初始结构，每个元素的父元素都是自己，表示互不相连

经过一系列变换连接后

ele: 0 1 2 3 4 5 6 7 8 9 parent : 0 1 2 8 3 5 5 7 8 8

代码如下：

public class UnionFindTwo { private int[] parent; // parent表示父元素 private int count; public UnionFindTwo(int n){ count = n; parent = new int[n]; for(int i=0;i<n;i++){ parent[i] = i; } } // 找根节点，只要p的parent是自己，就是根节点 int find(int p){ assert (p>=0 && p<count); while(p!=parent[p]){ p = parent[p]; } return p; } // 两个元素的根节点相等，表示相连 boolean isConnected(int p,int q){ return find(p)==find(q); } // 连接 void union(int p,int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot==qRoot){ return; } // 将一个根作为另一个根的父，两树相连 parent[pRoot] = qRoot; } }

三、union的低rank优化

虽然union优化成了O（1）级别的了，但是将两根节点相连具有随机性，很可能导致树深度变大。

public class UnionFindThree { private int[] parent; private int[] rank; // rank[i]表示以i为根的集合的树的层数 private int count; public UnionFindThree(int n){ count = n; parent = new int[n]; rank = new int[n]; for(int i=0;i<n;i++){ parent[i] = i; rank[i] = 1; // 初始化的节点互不相连，树层数都为1 } } // 找到parent是自己为止 int find(int p){ assert (p>=0 && p<count); while(p!=parent[p]){ p = parent[p]; } return p; } boolean isConnected(int p,int q){ return find(p)==find(q); } // (4-->3-->8,9)将元素少的集合根节点 指向 元素多的集合的根节点 void union(int p,int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot==qRoot){ return; } // rank小的根指向指向rank大的根，根不会变化，只有相等时会rank会大1 if(rank[pRoot]< rank[qRoot]){ parent[pRoot] = qRoot; }else if(rank[pRoot]> rank[qRoot]){ parent[qRoot] = pRoot; }else{ parent[pRoot] = qRoot; rank[qRoot]+=1; } } }

四、路径压缩（优化find）

在find（p）操作中，如果父不是本身，说明不是根，则继续往上找。 有个巧妙的优化办法，就是：当p的parent不是p时，让p的parent的parent成为p的parent

这样的好处就是，越过了上述的 元素3直接检查元素2，跳级完成寻根的动作。假如3就是根元素，那么3的parent就是自己，4指向3充其量就是没有变动罢了，不会有任何问题。

同理，考察元素2时，也是压缩寻根。 压缩的好处时：下次访问时更优

核心代码

int find(int p){ assert (p>=0 && p<count); while(p!=parent[p]){ // 路径压缩 parent[p] = parent[parent[p]]; // 继续寻根，与之前相同 p = parent[p]; } return p; }

这样的压缩，不是最优的，最优的压缩应该可以压缩到两层

利用递归，如果父元素不是自己，就将父元素的根指向自己（父元素的根自然时自己的根），如此递归，直到根=根的父，返回根的父也就是根本身。这样既找到了跟元素，而且目标元素的父也成了根元素。

public class UnionFindFour { private int[] parent; private int[] rank; // rank[i]表示以i为根的集合的树的层数 private int count; public UnionFindFour(int n){ count = n; parent = new int[n]; rank = new int[n]; for(int i=0;i<n;i++){ parent[i] = i; rank[i] = 1; } } // 找到parent是自己为止 int find(int p){ assert (p>=0 && p<count); // while(p!=parent[p]){ // parent[p] = parent[parent[p]]; // p = parent[p]; // } if(p!=parent[p]){ // 递归查询根元素 parent[p] = find(parent[p]); } return parent[p]; } boolean isConnected(int p,int q){ return find(p)==find(q); } // (4-->3-->8,9)将元素少的集合根节点 指向 元素多的集合的根节点 void union(int p,int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot==qRoot){ return; } if(rank[pRoot]< rank[qRoot]){ parent[pRoot] = qRoot; }else if(rank[pRoot]> rank[qRoot]){ parent[qRoot] = pRoot; }else{ parent[pRoot] = qRoot; rank[qRoot]+=1; } } }