什么是并查集

image.png

并查集接口：

  1. public interface UF {
  2.     int getSize();
  3.     boolean isConnected(int p,int q);
  4.     void unionElements(int p,int q);
  5. }

Quick Find

  1. public class UnionFind1 implements UF{
  2.     //存储相应元素的集合编号
  3.     private int[] id;
  5.     public UnionFind1(int size){
  6.         id=new int[size];
  7.         for(int i=0;i<id.length;i++){
  8.             id[i]=i;
  9.         }
  10.     }
  12.     @Override
  13.     public int getSize() {
  14.         return id.length;
  15.     }
  17.     //元素属于同一个集合，则这两个元素就是相连的
  18.     //时间复杂度：O(1)
  19.     @Override
  20.     public boolean isConnected(int p, int q) {
  21.         return find(p)==find(q);
  22.     }
  24.     //查找p元素所属的集合
  25.     private int find(int p){
  26.         if(p<0 || p>=id.length){
  27.             throw new IllegalArgumentException("p is out of bound");
  28.         }
  29.         return id[p];
  30.     }
  32.     //时间复杂度：O(n)
  33.     @Override
  34.     public void unionElements(int p, int q) {
  35.         int pId=find(p);
  36.         int qId=find(q);
  37.         if(pId==qId){
  38.             return;
  39.         }
  40.         //连接两个元素后，如果它们是在两个不同的集合中，
  41.         //则现在由于p、q的连接，就会成为一个集合
  42.         for(int i=0;i<id.length;i++){
  43.             if(id[i]==pId){
  44.                 id[i]=qId;
  45.             }
  46.         }
  47.     }
  48. }

image.pngimage.png

Quick Union

初始化并查集，每个节点指向自身，构成了森林。

image.png

union(4,3)，就是将4的父指针指向3，也就是说，此时3是4的父节点

image.png

union(9,4)，就是将9的父指针指向4所在集合的根节点

image.png

  1. public class UnionFind2 implements UF{
  2.     //parent[i]表示i所指向的父节点
  3.     private int[] parent;
  5.     public UnionFind2(int size){
  6.         parent=new int[size];
  7.         //初始化时，将每个元素看成一个树节点，它们指向自身，构成森林
  8.         for(int i=0;i<parent.length;i++){
  9.             parent[i]=i;
  10.         }
  11.     }
  13.     @Override
  14.     public int getSize() {
  15.         return parent.length;
  16.     }
  18.     //查找p元素所在的树（也就是集合）的根节点
  19.     //时间复杂度：O(h),其中h为该集合树的深度
  20.     private int find(int p){
  21.         if(p<0 || p>=parent.length){
  22.             throw new IllegalArgumentException("p is out of bound.");
  23.         }
  24.         while(p!=parent[p]){
  25.             p=parent[p];
  26.         }
  27.         //返回的是p所在的集合的编号，同时也是p集合非根节点
  28.         return p;
  29.     }
  31.     @Override
  32.     public boolean isConnected(int p, int q) {
  33.         //根节点相同，就是同一个集合
  34.         return find(p)==find(q);
  35.     }
  38.     @Override
  39.     public void unionElements(int p, int q) {
  40.         int pRoot=find(p);
  41.         int qRoot=find(q);
  42.         if(pRoot==qRoot){
  43.             return;
  44.         }
  45.         //将p所在集合的根节点指向q所在集合的根节点
  46.         parent[pRoot]=qRoot;
  47.     }
  48. }

基于size的优化

  • 对Union Find 2的改进：

根据两个元素所在的集合的元素个数的不同，判断合并方向。
将元素少的集合合并到元素多的集合上，降低树的高度。

  1. public class UnionFind3 implements UF{
  2.     //parent[i]表示i所指向的父节点
  3.     private int[] parent;
  4.     //sz[i]表示i元素所在的集合的元素个数
  5.     private int[] sz;
  7.     public UnionFind3(int size){
  8.         parent=new int[size];
  9.         sz=new int[size];
  10.         //初始化时，将每个元素看成一个树节点，它们指向自身，构成森林
  11.         for(int i=0;i<parent.length;i++){
  12.             parent[i]=i;
  13.             //初始化时，每个节点就是一个集合，那么元素个数就是1
  14.             sz[i]=1;
  15.         }
  16.     }
  18.     @Override
  19.     public int getSize() {
  20.         return parent.length;
  21.     }
  23.     //查找p元素所在的树（也就是集合）的根节点
  24.     //时间复杂度：O(h),其中h为该集合树的深度
  25.     private int find(int p){
  26.         if(p<0 || p>=parent.length){
  27.             throw new IllegalArgumentException("p is out of bound.");
  28.         }
  29.         while(p!=parent[p]){
  30.             p=parent[p];
  31.         }
  32.         //返回的是p所在的集合的编号，同时也是p集合非根节点
  33.         return p;
  34.     }
  36.     @Override
  37.     public boolean isConnected(int p, int q) {
  38.         //根节点相同，就是同一个集合
  39.         return find(p)==find(q);
  40.     }
  42.     //根据两个元素所在的集合的元素个数的不同，判断合并方向。
  43.     //将元素少的集合合并到元素多的集合上，降低树的高度。
  44.     @Override
  45.     public void unionElements(int p, int q) {
  46.         int pRoot=find(p);
  47.         int qRoot=find(q);
  48.         if(pRoot==qRoot){
  49.             return;
  50.         }
  51.         //将p所在集合的根节点指向q所在集合的根节点
  52.         //parent[pRoot]=qRoot;
  54.         //改进：
  55.         if(sz[pRoot]<sz[qRoot]){
  56.             //p节点所在的集合元素较少，pRoot的父指针指向qRoot
  57.             parent[pRoot]=qRoot;
  58.             sz[qRoot]+=sz[pRoot];
  59.         }else{
  60.             parent[qRoot]=pRoot;
  61.             sz[pRoot]+=sz[qRoot];
  62.         }
  63.     }
  64. }

基于rank的优化

对于如下并查集，union(4,2)

image.png

按照“基于size的优化”将8指向7，此时树的深度增加了。

image.png

我们应该是这样合并合理：将7指向8，树的深度没有增加，效率更高

image.pngimage.png

  • 基于rank的优化：rank[i]表示根节点为i的树的深度

根据两个元素所在的集合的树的深度不同，判断合并方向。
将深度浅的集合合并到深度深的的集合上，降低树的高度。

  1. public class UnionFind4 implements UF{
  2.     //parent[i]表示i所指向的父节点
  3.     private int[] parent;
  5.     //rank[i]表示根节点为i的树的深度
  6.     private int[] rank;
  8.     public UnionFind4(int size){
  9.         parent=new int[size];
  10.         rank=new int[size];
  11.         //初始化时，将每个元素看成一个树节点，它们指向自身，构成森林
  12.         for(int i=0;i<parent.length;i++){
  13.             parent[i]=i;
  14.             //初始化时，每个节点就是一个集合，那么元素所在集合的深度就是1
  15.             rank[i]=1;
  16.         }
  17.     }
  19.     @Override
  20.     public int getSize() {
  21.         return parent.length;
  22.     }
  24.     //查找p元素所在的树（也就是集合）的根节点
  25.     //时间复杂度：O(h),其中h为该集合树的深度
  26.     private int find(int p){
  27.         if(p<0 || p>=parent.length){
  28.             throw new IllegalArgumentException("p is out of bound.");
  29.         }
  30.         while(p!=parent[p]){
  31.             p=parent[p];
  32.         }
  33.         //返回的是p所在的集合的编号，同时也是p集合非根节点
  34.         return p;
  35.     }
  37.     @Override
  38.     public boolean isConnected(int p, int q) {
  39.         //根节点相同，就是同一个集合
  40.         return find(p)==find(q);
  41.     }
  43.     //根据两个元素所在的集合的树的深度不同，判断合并方向。
  44.     //将深度浅的集合合并到深度深的的集合上，降低树的高度。
  45.     @Override
  46.     public void unionElements(int p, int q) {
  47.         int pRoot=find(p);
  48.         int qRoot=find(q);
  49.         if(pRoot==qRoot){
  50.             return;
  51.         }
  52.         //将p所在集合的根节点指向q所在集合的根节点
  53.         //parent[pRoot]=qRoot;
  55.         /*改进：
  56.         if(sz[pRoot]<sz[qRoot]){
  57.             //p节点所在的集合元素较少，pRoot的父指针指向qRoot
  58.             parent[pRoot]=qRoot;
  59.             sz[qRoot]+=sz[pRoot];
  60.         }else{
  61.             parent[qRoot]=pRoot;
  62.             sz[pRoot]+=sz[qRoot];
  63.         }*/
  65.         //改进
  66.         if(rank[pRoot]<rank[qRoot]){
  67.             //pRoot集合的深度浅，pRoot的父指针指向qRoot
  68.             parent[pRoot]=qRoot;
  69.         }else if(rank[pRoot]>rank[qRoot]){
  70.             parent[qRoot]=pRoot;
  71.         }else{ //rank[pRoot]==rank[qRoot]
  72.             parent[pRoot]=qRoot;
  73.             //pRoot的父指针指向qRoot,则qRoot所在的集合深度+1
  74.             rank[qRoot]+=1;
  75.         }
  76.     }
  77. }

路径压缩I

前面的 Union Find 4的find(4)，算法过程：

image.png

路径压缩后，算法过程：

image.png

  1. //查找p元素所在的树（也就是集合）的根节点
  2. //时间复杂度：O(h),其中h为该集合树的深度
  3. private int find(int p){
  4.     if(p<0 || p>=parent.length){
  5.         throw new IllegalArgumentException("p is out of bound.");
  6.     }
  7.     while(p!=parent[p]){
  8.         parent[p]=parent[parent[p]];
  9.         p=parent[p];
  10.     }
  11.     //返回的是p所在的集合的编号，同时也是p集合非根节点
  12.     return p;
  13. }

路径压缩II

image.png

  1. //查找p元素所在的树（也就是集合）的根节点
  2. //时间复杂度：O(h),其中h为该集合树的深度
  3. private int find(int p){
  4.     if(p<0 || p>=parent.length){
  5.         throw new IllegalArgumentException("p is out of bound.");
  6.     }
  7.     if(p!=parent[p]){
  8.         parent[p]=find(parent[p]);
  9.     }
  10.     return parent[p];
  11. }