并查集

性质 并查集算法(union_find sets)不支持分割一个集合,求连通子图、求最小生成树 用法 并查集是由一个数组pre[],和两个函数构成的,一个函数为find()函数,用于寻找跟节点,第二个函数是mix()用于合并路线的 pre[i]: i表示元素,pre[i]表示该元素i所在的集合中的父节点为pre[i]

int Find(int x)  
{  
    //查找根节点
    int r=x;  
    while(r!=pre[r])  
        r=pre[r];  
     //压缩路径
    int i=x,j;  
    while(pre[i]!=r)  
    {  
        j=pre[i];  
        pre[i]=r;  
        i=j;  
    }  
    return r;  
}  
void mix(int x,int y)  
{  
    int fx=Find(x),fy=Find(y);  
    if(fx!=fy)  
    {  
        pre[fy]=fx;  
    }  
}

hdu1232

#include<iostream>  
using namespace std;  

int  pre[1050];  
bool t[1050];               //t 用于标记独立块的根结点  

int Find(int x)  
{  
    int r=x;  
    while(r!=pre[r])  
        r=pre[r];  

    int i=x,j;  
    while(pre[i]!=r)  
    {  
        j=pre[i];  
        pre[i]=r;  
        i=j;  
    }  
    return r;  
}  

void mix(int x,int y)  
{  
    int fx=Find(x),fy=Find(y);  
    if(fx!=fy)  
    {  
        pre[fy]=fx;  
    }  
}   

int main()  
{  
    int N,M,a,b,i,j,ans;  
    while(scanf("%d%d",&N,&M)&&N)  
    {  
        for(i=1;i<=N;i++)          //初始化   
            pre[i]=i;  

        for(i=1;i<=M;i++)          //吸收并整理数据   
        {  
            scanf("%d%d",&a,&b);  
            mix(a,b);  
        }  


        memset(t,0,sizeof(t));  
        for(i=1;i<=N;i++)          //标记根结点  
        {  
            t[Find(i)]=1;  
        }  
        for(ans=0,i=1;i<=N;i++)  
            if(t[i])  
                ans++;  

        printf("%d\n",ans-1);  

    }  
    return 0;  
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 蓝桥杯之奇怪的比赛

    题目 奇怪的比赛 某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪:每位选手需要回答10个问题(其编号为1到10),越后面越有难度。答对的,当前分数...

    小二哥
  • getline();和reserve();

    getline() 语法: istream &getline( char *buffer, streamsize num ); istre...

    小二哥
  • 201709-1

    试题编号: 201709-1 试题名称: 打酱油 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述 ...

    小二哥
  • LeetCode刷题DAY 25:和可被 K 整除的子数组

    给定一个整数数组A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。如输入

    三猫
  • 用 Python-Markdown 和 google-prettify 来处理 Markdown 和代码高亮

    这是Python中处理Markdown的一个库,可以把markdown语法转为html,如下:

    the5fire
  • 万余网友吐槽360弹窗恐吓欺骗用户

    用户1127987
  • Android进阶难题:普通公司的程序员跟BAT大公司的技术差距在哪?该如何选择?

    对比BAT这类公司跟普通公司的工程师,其实他们的差距其实本来不大,不管是谁都只是努力地做好自己的事情,只是大公司这类的机会要来得多。

    Android技术干货分享
  • Winpcap基础代码

    Winpcap基础代码     使用Winpcap进行网络数据的截获和发送都需要的一段代码: #include<PCAP.H> #pragma comment(...

    Florian
  • Android四大组件:关于Activity的知识都在这里了

    关于内存泄漏 & 性能优化,请看系列文章: Android性能优化:这是一份全面&详细的内存优化指南 Android性能优化:手把手带你全面了解 内存泄露 ...

    Carson.Ho
  • 【许晓笛】EOS 新增的 WebAssembly 解释器,是什么鬼?

    Daniel Larimer 在最近的博客中透露,EOS 新增了官方的 WebAssembly 解释器,用来解释执行 WebAssembly 智能合约,加上之前...

    圆方圆学院

扫码关注云+社区

领取腾讯云代金券