并查集+路径压缩

概述感觉这篇文章总结的挺好的，转自https://www.cnblogs.com/lisijie/p/7694791.html int parent[MAX_N]  //父节点 int rank[MAX_N]   //树的高度 初始化： void init(int n){ for (int i=0;i<n;i++) { parent[i]=i; 感觉这篇文章总结的挺好的，转自https://www.cnblogs.com/lisijie/p/7694791.html

int parent[MAX_N]  //父节点

int rank[MAX_N]   //树的高度

初始化：

voID init(int n){    for (int i=0;i<n;i++)     {          parent[i]=i;           rank[i]=0;     }}

 

查询根节点：

int Find(int x){    if (parent[x]==x)     return x;    else      return parent[x]=Find(parent[x]);}

 

合并集合：

voID Unite(int w,int v){    int x=Find(w);    int y=Find(v);
    if（x==y) return ;

    if (rank[x]<rank[y])
       parent[x]=y;
    else{
       parent[y]=x;
       if (rank[x]==rank[y]) rank[x]++;
        parent[x]=y;}

 

路径压缩：

①递归：

int Find(int x)       //查找x元素所在的集合,回溯时压缩路径{    if (x != parent[x])    {        parent[x] = Find(parent[x]);     //回溯时的压缩路径    }         //从x结点搜索到祖先结点所经过的结点都指向该祖先结点    return parent[x];}

 

②非递归：

int Find(int x){    int k,j,r;    r = x;    while(r != parent[r])     //查找跟节点        r = parent[r];      //找到跟节点，用r记录下    k = x;            while(k != r)             //非递归路径压缩 *** 作    {        j = parent[k];         //用j暂存parent[k]的父节点         parent[k] = r;        //parent[x]指向跟节点         k = j;                    //k移到父节点    }    return r;         //返回根节点的值            }

总结

以上是内存溢出为你收集整理的并查集+路径压缩全部内容，希望文章能够帮你解决并查集+路径压缩所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。