ToB企服应用市场:ToB评测及商务社交产业平台

标题: 并查集 [打印本页]

作者: 缠丝猫 时间: 2022-9-2 22:16
标题: 并查集
并查集学习知识点

·并查集概念
·并查集的基础操作：初始化、合并与查询
·并查集优化1：路径压缩
·并查集优化2：按秩合并(启发式合并)
·带权并查集
·种类并查集
引入：

话说在江湖中散落着各式各样的大侠，他们怀揣着各自的理想和信仰在江湖中奔波。或是追求武林至尊，或是远离红尘，或是居庙堂之高，或是处江湖之远。尽管大多数人都安分地在做自己，但总有些人会因为彼此的信仰不同而聚众斗殴。因此，江湖上常年乱作一团，纷纷扰扰。
这样长期的混战，难免会打错人，说不定一刀就把拥有和自己相同信仰的队友给杀了。这该如何是好呢？于是，那些有着相同信仰的人们便聚在一起，进而形成了各种各样的门派，比如我们所熟知的“华山派”、“峨嵋派”、“,崆峒派”、“少林寺”、“明教”……这样一来，那些有着相同信仰的人们便聚在一起成为了朋友。以后再遇到要打架的事时，就不会打错人了。

但是新的问题又来了，原本互不相识的两个人如何辨别是否共属同一门派呢?
这好办！我们可以先在门派中选举一个“大哥”作为话事人（也就是掌门人，或称教主等）。这样一来，每当要打架的时候，决斗双方先自报家门，说出自己所在门派的教主名称，如果名称相同，就说明是自己人，就不必自相残杀了，否则才能进行决斗。于是，教主下令将整个门派划分为三六九等，使得整个门派内部形成一个严格的等级制度（即树形结构）。教主就是根节点，下面分别是二级、三级、……、N级队员。每个人只需要记住自己的上级名称，以后遇到需要辨别敌友的情况时，只需要一层层往上询问就能知道是否是同道中人了。

数据结构的角度来看：
由于我们的重点是在关注两个人是否连通，因此他们具体是如何连通的，内部结构是怎样的，甚至根节点是哪个（即教主是谁），都不重要。所以并查集在初始化时，教主可以随意选择（就不必再搞什么武林大会了），只要能分清敌友关系就行。
备注：上面所说的“教主”在教材中被称为“代表元”。
即：用集合中的某个元素来代表这个集合，则该元素称为此集合的代表元。

什么是并查集？

在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内竞赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往超过了空间的限制，计算机无法承受；即使在空间上能勉强通过，运行的时间复杂度也极高，根本不可能在比赛规定的运行时间内计算出试题需要的结果，只能采用一种特殊数据结构——并查集来描述。
·举一个例子
设初始有若干元素：1,2,3,4,5,6,7,8
元素之间有若干关系：1~3,2~4,5~6,3~5,7~8,4~8
关系合并过程：
初始 {1},{2},{3},{4},{5},{6},{7},{8}
1~3：{1,3},{2},{4},{5},{6},{7},{8}
2~4：{1,3},{2,4},{5},{6},{7},{8}
5~6：{1,3},{2,4},{5,6},{7},{8}
3~5：{1,3,5,6},{2,4},{7},{8}
7~8：{1,3,5,6},{2,4},{7,8}
4~8：{1,3,5,6},{2,4,7,8}
并查集概念

并查集(Disjoint-Set或Union-Find Set)是一种表示不相交集合的数据结构，用于处理不相交集合的合并与查询问题。在不相交集合中，每个集合通过代表来区分，代表是集合中的某个成员，能够起到唯一标识该集合的作用。一般来说，选择哪一个元素作为代表是无关紧要的，关键是在进行查找操作时，得到的答案是一致的(通常把并查集数据结构构造成树形结构，根节点即为代表)。在不相交集合上，需要经常进行如下操作:
·findSet(x):查找元素 x 属于哪个集合，如果 x 属于某一集合，则返回该集合的代表。
·unionSet(x，y):如果元素 x 和元素 y 分别属于不同的集合，则将两个集合合并，否则不做操作。
并查集的实现方法是使用有根树来表示集合——树中的每个结点都表示集合的一个元素，每棵树表示一个集合，每棵树的根结点作为该集合的代表。

并查集基础操作：初始化

现共有N个元素，对这N个元素要进行查询与合并操作，现进行初始化；例如N = 10，初始化方法如下，father为i的父结点编号，初始化时结点的父结点为本身，即自己代表自己，建立N个独立集合：
[code]void MakeSet(int n) { for (int i = 1; i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4