并查集

int FindSet(int x){

    int px = x;

    while(px != p[px])//当px不是树根,就一直往上冒

        px = p[px];

    while(x != px){//做一点优化,把路径上的结点的父结点全部设为根

        int temp = p[x];

        p[x] = px;

        x = temp;

    }

    return px;

}

void UnionSet(int x, int y){

    x = FindSet(x);

    y = FindSet(y);

    if(Rank[x] > Rank[y])

        p[y] = x;

    else{

        p[x] = y;

        if(Rank[x] == Rank[y])

            Rank[y]++;

    }

}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 并查集 星期五花了一个小时敲完了并查集代码,花了大部分时间去调试结果发现问题源头出在eclipse重定向中与我自身...
    赵志文学编程阅读 183评论 0 1
  • 某次参加笔试的最后一题大意如下:给定一组用户[0..n],以及他们之间的好友关系,问这些好友构成了多少个朋友圈?例...
    Realizability阅读 1,585评论 0 0
  • function UnionFind(row, col, idx){ var o = new Object(); ...
    XiangCheng阅读 514评论 0 1
  • 编辑:数字_ID 时间:2018年5月22日 1. 写在题前 一道非常经典的且有意思的并查集题目,所以打算放上原题...
    数字_ID阅读 486评论 0 0
  • “妈妈 ,你就让我去吧!”我费了好多的口舌,才证得妈妈的同意去参加一场葬礼,我的脚触碰的大地的那一刻,我就想起了...
    郑潇榕阅读 203评论 0 0