并查集详解（原理+代码实现+应用+优化）_单向并查集代码

这篇文章我们来学习一个数据结构叫做并查集！

1. 并查集概念

首先我们来了解一下并查集的概念：

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。
适合于描述这类问题的抽象数据结构称为并查集(union-find set)。

2. 并查集原理

那下面我们通过一个小故事给大家讲解一下并查集的原理

假设某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}；
毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。

这里呢它们就按照编号分成了三个集体。
那我们如何表示不同的集合呢？

那上面我们了解过了概念，并查集呢通常用森林来表示，一棵树就是一个集合。

上面是按编号分的，那如果我们拿到的是同学的名字，我如何知道它对应的编号是几呢？

那我就可以把名字和编号建立一个映射关系。

那我们来写写代码：

假设我们拿到的是一个名字的数组，个数为n
那我们如何存储这些数据并跟编号建立映射呢？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/792325