并查集实现

并查集是什么东西？

它是用来管理元素分组情况的一种数据结构。

他可以高效进行两个操作：

1. 查询a，b是否在同一组
2. 合并a和b所在的组

萌新可能不知所云，这个结构到底有什么用？

经分析，并查集效率之高超乎想象，对n个元素的并查集进行一次操作的复杂度低于O(logn)

我们先说并查集是如何实现的：

也是使用树形结构，但不是二叉树。

每个元素就是一个结点，每组都是一个树。

无需关注它的形状，或哪个节点具体在哪个位置。

初始化：

我们现在有n个结点，也就是n个元素。

合并：

然后我们就可以合并了，合并方法就是把一个根放到另一颗树的下面，也就是整棵树作为人家的一个子树。

查询：

查询两个结点是否是同一组，需要知道这两个结点是不是在一棵树上，让他们分别沿着树向根找，如果两个元素最后走到一个根，他们就在一组。

当然，树形结构都存在退化的缺点，对于每种结构，我们都有自己的优化方法，下面我们说明如何避免退化。

1. 记录每一棵树的高度，合并操作时，高度小的变为高度大的子树即可。
2. 路径压缩：对于一个节点，只要走到了根节点，就不必再在很深的地方，直接改为连着根即可。进一步优化：其实每一个经过的节点都可以直接连根。

这样查询的时候就能很快地知道根是谁了。

下面上代码实现：

和很多树结构一样，我们没必要真的模拟出来，数组中即可。

  

   

    

     

    
    

     

      int p[MAX_N];//父亲
     
    
   

    

     

    
    

     

      int rank[MAX_N];//高度
     
    
   

    

     

    
    

     

      //初始化
     
    
   

    

     

    
    

     

      void gg(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0;i<n;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p[i]=i;//父是自己代表是根
     
    
   

    

     

    
    

     

       rank[i]=0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //查询根
     
    
   

    

     

    
    

     

      int find(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(p[x]==x)return x;
     
    
   

    

     

    
    

     
 return p[x]=find(p[x])//不断把经过的结点连在根
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //判断是否属于同一组
     
    
   

    

     

    
    

     

      bool judge(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return find(x)==find(y);//查询结果一样就在一组
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //合并
     
    
   

    

     

    
    

     

      void unite(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(x==y)return;
     
    
   

    

     

    
    

     
 if(rank[x]<rank[y])p[x]=y;//深度小，放在大的下面
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p[y]=x;
     
    
   

    

     

    
    

     
 if(rank[x]=rank[y])rank[x]++;//一样，y放x后，x深度加一
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

实现很简单，应用有难度，以后有时间更新题。

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/82663647