【计算机本科补全计划】图的连通性check by 并查集Union Find

正文之前

前几天苦练图论,虽然还不算登堂入室?但是好歹还是懂了好几个概念,今天就讲讲我最开始认识的一个,很棒的检查图的连通性的算法--并查集!!!

正文

具体的想法来自一篇写的超好的博客,如果底子不是很好,建议看下面这篇,当然如果可以给我顺手点个赞就更好了!!

http://blog.csdn.net/dellaserss/article/details/7724401

具体的代码如下:

#include<iostream>
using namespace std;

// 定义全局变量,作为并查集!! uf 取自:union find 
int uf[100]; 

//定义并查集的查找根节点的函数
int Find_set(int x)
{

    int s=x;
    while(uf[s]!=s)
        s=uf[s];
    int d=x,j;
//路径压缩算法
    while(uf[d]!=d)
    {
        j=uf[d];
        uf[d]=s;
        d=j;
    }
    return s;
}

// 定义图的整合算法
void mix(int x,int y)
{
    int s=Find_set(x);
    int d=Find_set(y);
    if(s!=d)
        uf[s]=d;
}

int main()
{
    int size,num_of_tuple,a,b,root_point;
    cin>>size>>num_of_tuple;
//初始化并查集数组
    for (int i = 0; i < size; ++i)
    {
        uf[i]=i;
    }

// 进行路径的初始化
    for (int i = 0; i < num_of_tuple; ++i)
    {
        cin>>a>>b;
        mix(a,b);
    }
    for (int i = 0; i < size; ++i)
    {
        cout<<"第 "<<i<<" 个元素的父亲是:"<<uf[i]<<" 根节点是: "<<Find_set(i)<<endl;
    }
    return 0;

}

下面我来说说,这个东西是怎么一回事:

并查集本身是一个数组,每个元素都有自己的编号,也就是常用的下标, 每个下标对应的a[i] 都有一个数,这个数初始化的时候 是i ,但是之后 路径初始化的时候,我们进行扰乱。把每个下标对应的值,指向这个下标所表示的节点的父节点,层层叠叠 下来,最终就形成了一条通路。每一个节点都有自己的父节点与根节点,当然,对于最终的根节点来说,父节点与根节点都是自己,所以这才是根节点。根节点的选择没有依据,完全按照你的输入顺序不同而有不同的根节点,不过根节点不重要,我们需要的是验证图的连通性。比如我想检验 4 6 两个节点是否联通,那么我们只需要检查两个节点的根节点是不是一个就行了。因为一个联通的图里面是不会有两个根节点的,在图的整合过程中,两个不联通的图,通过mix算法整合。也就是说一个根节点放弃了自己根节点的身份,成为另一个根节点的子节点。所以只要是联通的图,就会只存在一个根节点,如果两个子节点的最终根节点不相等,可以肯定的是:这两个子节点不在同一个图内,就检查了连通性了!!

~~(PS: 盗图狗走一波)~~

还有一个就是路径的压缩。当我们的一个子节点检查到自己父节点还有父节点的时候,这个子节点就循循善诱的找到自己的根节点,然后直接管根节点叫爸爸,把自己原来的父节点彻底抛弃。所有的节点都这么干,最后每个联通的图就成了一个菊花状的连通图了!!

正文之后

今天下午就是CCF CSP第十二届计算机能力资格认证考核了。。好激动,四个小时,不知道能拿多少分?既然可以带纸质资料,那我就把《C++ Primer》 《算法竞赛入门经典训练指南》带进去,然后把我写的那些代码全部打印出来带过去吧!毕竟那么多呢!现在就好好的整理吧~ 待会一点出发去打印,一点半考试,时间上应该来得及~~

原文发布于微信公众号 - 工科狗和生物喵(gh_3507b116a1f8)

原文发表时间:2018-04-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

机器学习如何从 Python 2 迁移到 Python 3

关键时刻,第一时间送达! ? 本文经授权转自人工智能头条。 Python 已经成为机器学习及其他科学领域中的主流语言。它不但与多种深度学习框架兼容,而且还包含优...

3206
来自专栏Pythonista

Python之路,Day1 - Python基础1

python的创始人为吉多·范罗苏姆(Guido van Rossum)。1989年的圣诞节期间,吉多·范罗苏姆为了在阿姆斯特丹打发时间,决心开发一个新的脚本解...

1985
来自专栏安恒网络空间安全讲武堂

赛前福利②最新2018HITB国际赛writeup

FIRST 距离“西湖论剑杯”全国大学生网络空间安全技能大赛只有9天啦! 要拿大奖、赢offer,那必须得来点赛前练习定定心啊~这不,讲武堂就拿到了2018HI...

3374
来自专栏鸿的学习笔记

聊聊一些垃圾回收算法

不是所有的GC都是完美的,每一个GC算法的选用都有其背后的原因。而我们选择GC算法,有四个评价标准:吞吐量(也就是说,在单位时间内你回收的对象(这里是指通过应用...

792
来自专栏ImportSource

设计模式-抽象类,只是想为你做更多

如果说面向对象中的接口是把所有的事情扔给你的话,那么抽象类显然是想要为你做一些事情,如果实在有一部分做不了再扔给你。 相信对于大部分业务开发的场景下都不太会需要...

3667
来自专栏工科狗和生物喵

【计算机本科补全计划】指令:计算机的语言(MIPS) Part3

正文之前 今天学的很尴尬,因为有事情,而且新认识了两个计算机学院的保研大佬,不得不感叹我找的导师之强,第一个去上交的,是被金老师推荐去的,听说是跟了目前亚洲第一...

3288
来自专栏Jerry的SAP技术分享

如何用JavaScript实现2+2=5?

我大学毕业找工作时,经常做一些稀奇古怪的面试题。这不,给大家分享一道整蛊的面试题,它其实不能算一道正式的面试题,大家可以用它来捉弄你们那些程序员朋友。

1021
来自专栏H2Cloud

python的解释器spython介绍

Python解释器spython介绍 简介   出于个人爱好和某种需求,我再16年对python的解释器产生了浓厚兴趣,并且下定决心重新实现一个版本。我个人再游...

4035
来自专栏数据科学学习手札

(数据科学学习手札31)基于Python的网络数据采集(初级篇)

  在实际的业务中,我们手头的数据往往难以满足需求,这时我们就需要利用互联网上的资源来获取更多的补充数据,但是很多情况下,有价值的数据往往是没有提供源文件的直接...

48213
来自专栏新智元

Go 2.0发布在即,程序员有太多话要说

Go语言的开发者正着手准备开发2.0版本,并从以下三个方面发布了初步的设计方案(非官方正式版),以供社区开展讨论:

7801

扫码关注云+社区

领取腾讯云代金券