并查集

void Make_set(int n)
{
    for(int i=0;i<=n;i++)
    {
        father[i]=i;
        rank[i]=0;
    }
}

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;         //返回根节点的值            
}

void Union(int x,int y)
{
    if(x==y)return;
    if(rank[x]>rank[y])
    {
        father[y]=x;
    }
    else
    { //rank[x]<rank[y],也是father[x]=y,所以省略
        if(rank[x]==rank[y])
        {
            rank[y]++;
        }
        father[x]=y;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Remove Duplicates from Sorted Array

    问题:将有序的数组中重复的数字去掉 分析:由于有序所以只用和前一个比较就行 class Solution { public: int removeDup...

    用户1624346
  • HDU 2011 菜鸟杯

    A:该题写了很久,一直TLE,主要是枚举到n/2时间复杂度实在太高了,其实嘛,这道题就是因式分解,所以就是i*i=n,也就是sqrt(n) #include<s...

    用户1624346
  • hdu 1498 50 years, 50 colors(二分匹配,最小点覆盖)

    题意:n*n的矩阵放置不同的颜色(不同的数字代表不同的颜色),你有k次选择,每一次只能选择某一行或某一列,可以消除该行(列)的所有颜色,问有哪几种颜色,无论怎样...

    用户1624346
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

    查询区间 [ id-k,id+k] 小于 val 的个数 num , 再在该区间查询第 num 大的数。

    用户2965768
  • UVA 10462 Is There A Second Way Left?(带重边次小生成树)

    题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=...

    Ch_Zaqdt
  • Poj 1564 || HDU 1258 Sum It Up(dfs+技巧)

          题意就是先输入n,m,然后输入m个数,问在这m个数里有多少种任意相加起来等于n的方法,并且输出这些相加的数。

    Ch_Zaqdt
  • 逆元模板

    对于(a/b)%m==? 1.当m是素数的时候,根据费马小定理,直接输出b^(n-2)即可 2.否则,扩展欧几里得exgcd(b,m,x,y) 1 #incl...

    attack
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051
  • 图的构建

    每天学Java
  • P1576 最小花费

    题目背景 题目描述 在n个人中,某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费,请问...

    attack

扫码关注云+社区

领取腾讯云代金券