并查集讲解
admin
2024-01-29 00:13:06
0次

并查集

顾名思义，对集合进行合并和查找操作。
合并：将两个集合或元素合并成一个。
查找：查找两个元素是否在同一集合中。
实现：通过建立一个father数组，即一个父亲节点 数组，记录这一个节点的父亲节点，并且父亲节点也在此集合内。
！！！同一集合中只存在一个根结点，这个根结点是这个集合中所有元素的根结点，是整个集合的编号。

模板step:
1.初始化
一开始所有节点都是独立的，那么就要将其父亲节点设置为他们自己来表明自身是独立的。

for(int i=0;ifather[i]=i;
}

2.查找
一个集合必须要有一个根结点来表示，那么我们可以通过递归不断查找父亲节点。从而找到根结点老祖宗。

int find(int x)
{if(father[x]==x){//如果我是老祖宗那么就返回祖宗节点return x;}else{//如果我不是，那就判断我爸爸是不是return find(father[x]);}
}

3.合并
将两个集合合并成一个集合，只有属于两个不同集合的元素才能合并，分两步
step1：判断两个人是不是一个集合的(是不是一个老祖宗)
step2：如果不是那么进行合并操作

void Union(int a,int b)
{int fathera=find(a);//查找a的祖宗int fatherb=find(b);//查找b的祖宗if(fathera!=fatherb){fa[fatherb]=fathera;}
}

!!!不能简单地将这个元素的父亲设为另一个元素，是fa[fatherb]=fathera;而不是fa[b]=fathera;

优化

int find(int x){if(father[x]==x){return x;}else{return father[x]=find(father[x]);//直接将根结点赋值为当前节点的父亲节点。}
}

借鉴这位小姐姐的博客，直通车~

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：开放第三方下载 苹果历史性让步 开放第三方下载 苹果历史性让步

下一篇：多特vs波鸿：桑乔迎回归后的主场首秀，迈尔、穆科科出战 多特蒙德vs波鸿首发阵容 多特波鸿友谊赛首发

相关内容

热门资讯

原创 4... 写在文章前的声明：在本文之前的说明：本文中所列的投资信息，只是一个对基金资产净值进行排行的客观描述，...
胜宏科技港股大涨49% 做完英... 记者 陈月芹 4月21日，全球AI算力板龙头胜宏科技（02476.HK）登陆港交所，上市首日股价大涨...
永赢基金：聚焦“科技新锐”，科... 数据来源：Wind，时间统计区间为2025/1/1-2026/4/21，指数过往表现不预示未来，不构...
五大阅读趋势显现！当当网发布2... 在第31个世界读书日即将来临之际及首个全民阅读活动周期间，当当网正式发布2026国民阅读洞察报告。 ...
业绩逐季回暖 老百姓大药房一季... 上证报中国证券网讯（记者 夏子航）4月22日晚，老百姓大药房发布2025年年报和2026年一季报。今...
中国20强城市大洗牌：苏州接近... 中国的城市经济竞争格局一直在变化，每年发布的GDP数据都会对城市经济实力进行重新排列。2025年榜又...
直击金宏气体股东会：预期年内氦... 《科创板日报》4月22日讯（记者 郭辉）金宏气体日前举行2025年度股东大会。会上该公司审议了公司年...
5月1日起，俄据悉将叫停哈萨克... 据行业消息人士透露，俄罗斯将于5月1日起停止经友谊管道转运哈萨克斯坦输往德国的石油，相关调整计划已送...
深化具身智能生态布局 京东携手... 4 月 22 日，京东与国内消费级人形机器人头部企业松延动力正式达成三年期战略合作。双方将围绕产品研...
原创 帮... 先问你一个问题，美伊停火今晚到期，按常理避险情绪该升温，黄金应该涨吧？结果恰恰相反——原油涨了，黄金...
300295、600889，将... 三六五网、南京化纤，将被*ST。 公司股票自4月23日开市起停牌一天，于4月24日开市起复牌并实施退...
能源大变天！外媒：羡慕中国的石... 这一次油价突破 110 美元的能源危机，着实魔幻。如果放在十年前，没人会相信中国能在这场风波中获利，...
衡水老白干：2025年营收41...
黄金涨跌两难，现在还能上车吗？ 中新网4月22日电(记者 左雨晴) 四月以来，美伊局势反复拉扯，美联储降息预期一变再变。黄金价格在4...
“我身体健康”，库克现身员工大... 当地时间4月21日，受苹果官宣CEO换届影响，公司股价盘中下探超2%，总市值失守4万亿美元关口，收盘...
库克留下一个悬念 工程师能否拯救创新节奏？ 听筒Tech（ID:tingtongtech）原创 文 | 赵 森 ...
探索消费信贷与社交支付深度融合... 腾讯这一金融产品再添新功能，4月19日，北京商报记者注意到，微信分付灰度测试转账功能引发热议，在向微...
土耳其主要银行股指早盘下跌2% 每经AI快讯，4月20日，土耳其主要银行股指早盘下跌2%。 每日经济新闻
好用的OTA代运营源头厂家 在如今竞争激烈的酒旅行业中，OTA代运营服务成为了众多酒店、民宿提升竞争力的关键。但市场上的代运营厂...
成都五一出游全国热门第三 “五一”假期临近，同程旅行最新发布的《2026“五一”旅行趋势报告》显示，今年“五一”期间成都同时位...