5.4.4并查集

٩(⊙o⊙*)و好！很有精神 ！ 费曼学习法我挑战背诵小哥哥讲稿讯飞翻得还是有一些错误喽

我觉得大家好，上一节课我们结束了所有有关数的基本概念的学习，那么本节课我们就来学习一个数的小应用，叫做并查集什么是并查集呢？它其实是一种简单的集合表示在该结合当中有若干个数据元素，我们也通常把带集合划分为若干皋子集这些子集组成了给璇玑，那么有的同学可能会有疑问，为什么并查集城集合会与术的应用有关系呢？其实啊，我们通常用树的双亲表示法作为并查集的存储结构，也就是每个子集我们把它表示成一个数的形式，而且这些数组成了a并查集的森林，那么同学们要注意的是，我们这里用的是数的双心表示法作为存储结构，那么大家还记得双星表示法吗？在双星表示法中，我们会存放该节点双星节点的指针我们是用了一个数字而且我还规定通常用。下标的，而且我们还规定通常用数字元素下标代表元素名有根基点的下标代表子集合的名称，其中根据双子节点为复数，因为我们知道了这几点是没有双极节点的，我们用负数来标识它是。跟节点，并且我们还通常用该负数的绝对值表示该子集当中的节点数量，也就是该克数当中的节点数量好，这就是并查集，那么在并查集当中有哪些应用呢？其中第1个一定是一个初始化的应用叫initial s，其中这个传输参数是一个集合，它是如何进行初始化的呢？它是将其x升到每个元素都初始化为只有一个单元数的子集合，也就是如果该极客当中有n多元素有n多元素，那么我们就生成n个子集，也就是n个数，接下来是两个操作就是并和茶的操作，首先是并的操作，它的创作参数是集合s以及两个我们要并到子集后面叫做root1和root，2我们要注意的一点是，这里的root1和note2是互补相交的，如果它们有相同的部分我们将不予执行，它的具体操作是我们把其看最终到此集合操作操作。按照操作是不是查找操作，它创造参数是集合s以及查找元素s，那么接下来具体的操作是什么呢？它是查找集合s中单元数x所在的子集合并且返回该词结合到名字也就是它跟写点的标号，还有这就是有关并查集的三个操作，接下来我们来看一个并查询的，小意思，让大家理解，这是一个具有10个整形元素的集合，s从0~9，我们首先初始化时会把它分为10个子集合，每一个元素作为集合当中的一个元素，那么分别是x零一直到了s9，那么这样的10个子集合，我们用数应该怎样表示呢？它是不是就是10个根接点啊？从0~9这样的10个根基点，我们应该如何用孩子表示法来进行放呢？大家还记不记得当中数据。还记不记得我们要存放在这样一个数组当中，其中每一个数字数量分别是一个数据挺好的，一个就是因为我们是放到元素高的，数字是一致的，他释放的部分就可以了。还有最多就是微笑。元素刚好是从0~9，它与数到下落是一致的，所以我们也可以不存放day的部分，但是我们数据加标相同，我们只放排除法就可以了，好我们来观察每一个拍摄它的下标度是-1，因为每个节点都是登记点，所以他们都是负数，而且每一个点数只有一个节点，所以他们是-1，所以去年做了一个ERP，没啥好事，接下来我们来看，如果他们变成了三个子集合，也就是s0c1s2其中分为有0678149和235235，那么他们应该变成什么样的树型结构，什么样的树的形式呢？他会变成这样三棵树的形式，那么变成了这样三个字结合这样三个数，我们都一样存储他们的孩子，表示法的数组应该做出什么样的改变呢。什么样的数的形式呢，它会变成这样三棵树的形式，那么变成了这样三个字结合这样三棵树，我们都应当遵守它们的孩子表示法的数组应该做出什么样的改变呢？我们做出了这样的改变，我们来观察其中0节点，也就是0差标，它的判断的值为-4，因为它是一个根节点，所以它是一个负数bc平行点所在的数有4个节点，所以它称为-4，它的绝对值表示了该个数节点的个数，也就是x集合的元素个数，那么接下来我们来看节点1和节点2，它们都是数的根节点，也就是存放为一个负值，并且它们所在的数都有三个节点，所以它们都是-3第三个职位第四个基点同样也是所以存放

所以看到下标也就是1号门，按照这样的规则一次存放了，剩下的所有节点好，这就是我们变成了三个字，结合这样三棵树数字做出的改变，接下来我们来看并查集的语言实现，首先我们来看明沙棘的语言定义方法。数组不足作出大的改变，接下来我们来看这个茶几的语言实现，首先我们来看没茶几的语言定义方法，语言定义当中，我们用一个数组一个整形数组来表示了并查集，大家可能会有疑问，为什么我们可以用一个整形数组来表示并发起呢？明明它有数据部分以及指向双击节点下标的指针部分啊，其实在这里我们默认了数据与对应的数字下标是一致的，也就是数字下标是0的话，它的数据就是0，所以我们用一个整形变量仅存放它对应双击节点下标就可以了，如果数据对应对应不是与数组下标相同的话，我们可能还要用一个数组来存放数据部分，也可以用我们之前所学习过的结构体类型的数组来存放每一个节点其中包含了对下表的指针以及对应的数据定义了一个并查集操作参数是一个白色就是这一个。初始化，我们将每一个定义了一个并查集接着，第1个操作是初始化的操作初始化的传入参数是一个并发起，s也就是这一个整形数组，接着大家还记不记得如何进行初始化了，我们将每一个元素都初始化为一个子集合，也就是n个元素具有n个子集和n棵树，每一棵树当中只有一个节点元素，那么我们应该如何修改对应数组的双节点下标呢？我们将每一个节点的双击键下标都修改为-1，因为每个节点都是一棵树，而且每个树只有一个根结点，所以我们要将对应双节点下标的值修改为-1，how这就是初始化的步骤，修改完成之后，我们就完成了初始化的部分，接着依旧经过若干操作变成了这样的子集合，并且我们要修改对应数组的双击键下标好之后我们来介绍下两个操作，分别是病和茶的操作，如何实现查找操作呢？它的访问类型是一个整形变量，它返回的是我们查找到的结果。成了这样的集合，并且我们要修改对应数组的双击下，标好之后我们来介绍下两个操作分别是并和查的操作如何实现查找操作呢？它的访问类型是一个整形变量，他返回的是我们查找到的结果，他说35是一个并查记s以及所要查找的这个元素x，那么大家还记不记得我们查找什么呢？我们要查找这个元素在哪一个词，如果是正数的话，说明他不是根节点，我们要继续付出的话，我们就停止循环返回该根节点的数字下标好查找操作，最后我们看合并操作合并操作，不在我们看来是。接着。并且我们需要之后，我们来介绍下操作说明啥的操作，如何实现查找从坐到他的访问类型是一个整型变量，他返回的是我们查找到的结果，他说算术是一个b查解s以及所要查找的这个元素，x，那么大家还建立到我们要查找什么呢？我们要查找这个元素所在哪一个子集合你它的根节点的下标，所以我们利用了该手机指针，不断的向上查找，直到查找开课数的跟节点，也就是判断条件，判断它是否为正数，如果是正数的话，说明它不是根基点，我要继续循环查找，如果它是负数的话，我们将停止循环返回，该根节点的数字下标好，这就是查找操作，最后我们来看合并操作合并操作，它权重参数是一个平台写s以及两个子集合对应的操作非常简单。需要把第2部分节点就是如图2的对应到双击节点下标的值，修改为入则一就可以了，这样我们就实现了合并操作，例如在这个例子当中，如果我们要合并前两个子集合，我们只需要将一节点的双击节点的指针修改为0就可以了，这样我们是把一起点作为了临界点的孩子，起点我们完成了合并操作好，这就是并查集的三个操作的实现方式非常的简单的总结一下束河森林的相关知识