并查集及其应用

1、搜索集合及其应用。首先，举个例子。首先，描述一下关系问题：也许你不知道你的一个朋友是你的亲戚。他可能是你曾祖父的祖父的女婿的侄女的表弟的孙子！如果我们能得到一个完整的家谱，判断两个人是否有血缘关系应该是可行的。然而，如果两个人最接近的共同祖先与他们分离了几代，这使得家谱非常大，那么我们就没有能力去检验亲属之间的关系。在这种情况下，最好的帮手是电脑。为了简化问题，你会得到一些关于亲戚的信息，比如玛丽和汤姆是亲戚，汤姆和本是亲戚，等等。根据这些信息，你可以推断玛丽和本是亲戚。请尽快写一个程序来回答我们关于亲戚的问题。输入由两部分组成：第一部分以N和m开头。N是问题涉及的人数(1 N 20000)。

2、这些人的数量是1，2，3和n。下面有M行(1 M 1 000 000)，每一行有两个数字ai和bi，表明ai和bi是已知相关的。第二部分从Q开始。在下面的Q行中有Q个查询(1 Q 1 000 000)，每行都是ci和di，表示ci和di是否相关。输出：对于每个查询ci和di，输出一行：如果ci和di相关，则输出“是”，否则输出“否”。并搜索该集合及其应用，输入样本(关系。in):1072451389125633471089，输出样本(关系。out):是否是，搜索集合及其应用，问题分析：将每个人抽象为一个点，数据给出m条边的关系，当两个人是亲戚时，两点之间有一条边。得到一个有N个顶点和M条边的图

3、论模型是很自然的。请注意，图中连通块中的任何点都是相关的。对于最后的q个问题，判断两个顶点是否在同一个连通块中。用传统的思维，我们可以立即做出反应，为输入的n个点和m条边找出连通块，然后进行判断。然而，这种实现思想必须首先保存m条边，然后执行普通的遍历算法，这在空间和时间上都是低效的。经过进一步的考虑，如果题目的要求改变了，对于边和问题的交替输入，题目就变成：并搜索集合及其应用。第一行是N，m。N是问题涉及的人数(1 N 20000)。这些人的数字是1，2，3和n。下面有M行(1 M 2 000 000)，每行有三个数字ki，ai，bi，ai和bi，代表两个元素。ki是0或1，当ki是1时，意

4、味着这是边的信息，也就是说，意味着I和bi是相关的；当ki为0时，意味着这是一个问题。你应该根据旅行前获得的信息来判断ai和bi是否相关，并对每个问题回答是或否。这个问题比原来的问题更复杂，它需要两个随时回答问题的人之间的关系，并且可以立即合并两个相连的块进行信息提示。连通图的思想显然很难实现，因为它需要实时表达人与人之间的关系。并搜索集合及其应用，使用集合的思想为每个人建立一个集合。一开始，这个集合的元素是这个人自己，这意味着他一开始不知道任何人是他的亲戚。每当给定一个相对关系，这两个集合将被合并。这样，实时获得当前状态下的集合关系。如果有问题，请查看当前结果中的两个元素是否属于同一个集合。

5、样本数据说明如下：搜索集合及其应用，输入关系分离集合12345678910 (2，4) 12，435678910 (5，7) 12，435，768910 (1，3) 1，32，45，768910 (8 910 (5，6) 1，2，3，45，6，78，910 (2，3) 1，2，2的初始状态以收藏为理念，为每个人建立一个收藏。一开始，集合的元素是人本身。每当给定一个相对关系，这两个集合将被合并。这样，实时获得当前状态下的集合关系。如果有问题，请查看当前结果中的两个元素是否属于同一个集合。样本数据说明如下：从上图可以看出，运算是在集合的基础上进行的，不需要保存所有的边，每一步得到的划分方法都是动态

6、的。如何实现上述算法思想？我们将使用和搜索收藏。联合发现集及其应用：2.联合发现集的基本思想；1.union-find集合是用于分离集合操作的抽象数据类型。它处理集合之间的关系，也就是说，它动态地维护和处理集合元素之间的复杂关系。当给定两个元素的无序对(A，B)时，有必要快速“合并”A和B所在的集合，在此期间有必要重复“查找”元素所在的集合。单词“and”、“check”和“set”就是由此而来的。在这种数据类型中，n个不同的元素被分成几个组。每个组都是一个集合，称为不相交集合。搜索集支持查找一个元素所属的集合，并合并两个元素所属的集合。并搜索该集合及其应用。第二，例如，搜索集合的基本思想有这

7、样一个问题：最初，N个元素属于不同的N个集合。通过不断给出元素之间的联系，需要对元素之间的关系进行实时统计(无论是直接联系还是间接联系)。这时，有一个地方可以搜索和收集。元素之间是否有联系，只需判断两个元素是否属于同一个集合；为了建立元素之间的关系，我们只需要合并这两个元素所属的集合。这些操作由搜索集提供。并行搜索集本身没有结构，所以必须由一定的数据结构来支持和实现。数据结构的选择是一个重要的环节。选择不同的数据结构可能在搜索和合并的操作效率上有很大差异，但是操作实现相对简单有效。实现并行搜索数据结构的方法有很多，其中常用的有数组、链表和树。2.并行搜索的基本思想和并行搜索的数据结构记录了一组

8、分离的动态集S=S1、S2、SK。每个集合都由一个“代表”来标识，这意味着元素中的一个元素。哪个成员被选为代表并不重要。重要的是，如果动态集合的代表被获得两次，并且该集合在两个请求之间没有被修改，则两次获得的答案应该是相同的。动态集中的每个元素都由一个对象表示，让x表示一个对象，并行搜索集的实现需要支持以下操作：2 .并行搜索集支持的运算及其应用：2.并行搜索集的基本思想；2.并行搜索集MAKE-SET(x)支持的操作：创建一个只有成员(也是代表)的新集。因为每个集是分开的，所以要求x没有出现在其他集中。UNION(x，y):将包含x和y的动态集合(如Sx和Sy)合并成一个新集合，假设这两个集

9、合在此操作之前是分开的。结果集代表SxSy的一个成员。一般来说，在不同的实现中，Sx或Sy的代表通常被认为是新集合的代表。此后，原始的Sx和Sy被新的集S代替.FIND-SET(x):返回指向包含x的集合的代表，并行搜索及其应用；3.并行搜索的实现与优化：1.并行搜索的数组实现。实现并行搜索最简单的方法是用数组记录每个元素所属集合的个数。当搜索一个元素所属的集合时，只需要读取数组中记录的该元素所属集合的编号，时间复杂度为O(1)。当合并两个元素所属的集合时，需要将数组中属于一个集合的元素所对应的所有数组元素值都改变为另一个集合的数值，时间复杂度为O(n)。由于其实现简单，在实践中得到广泛应用。

10、虽然上面的数组实现很方便，但是合并的成本太高了。在最坏的情况下，将所有集合合并成一个集合的总成本可以达到O(n2)。联合搜索及其应用；3、联合搜索的实现与优化；2、实现链表的联合搜索，我们需要用一定的数据结构来组织动态集合，并且同一集合中的所有元素都应该是相关的。一个简单的想法是使用链表，每个集合对应一个链表，链表有一个头，每个元素有一个指向头的指针，指示它所属的类，还有一个指针指向它的下一个元素。同时，为了便于实现，指针last被设置为表示链表中的最后一个元素(页脚)。您可以选择一个静态数组(一般来说，这个问题处理的对象是连续的整数，您可以使用下标来对应元素)，并将记录定义为：类型节点=记录

11、头，下一个，最后一个：整数；结束；var S : array1.节点的最大数量；并行搜索及其应用，3。并行搜索的实现和优化。实现链表的并行搜索，我们可以得到MAKE-SET和FIND-SET的实现如下：MAKE-SET(x)sx . head=x；sx . next=0；FIND-SET(x)返回Sx.head的时间复杂度是O(1)。请注意，在我们采用链表后，当有两个元素(x，y)，FIND-SET(x)FIND-SET(y)对应不同的集合时，我们需要合并这两个链表。方法是将一个表的页眉直接连接到另一个表的页脚。这个操作非常简单，但是它不可避免地导致需要修改修改后的下一个表的所有头值，这需要线

12、性赋值、联合搜索及其应用；3.联合搜索的实现与优化：2.联合搜索链表的实现。现在我们讨论UNION(x，y)的实现，假设UNION(x，y)的参数是有序的，也就是说，y所属的集合被合并到x的集合中。当FIND-SET(x)FIND-SET(y)出现时，y的头部直接连接到x的尾部，y所在集合中所有元素的头部被设置为FIND-SET(x)。同时，x的页脚也应该被设置为原始y的页脚。请注意，最后一个指针只需要记录在标题节点中，因为每次找到FIND-SET(x)时都可以获得标题元素。而链表中的其他元素最后重新记录是没有意义的。考虑到输入数据的特殊性，我们总是把Y代入X，所以如果Y所在的集合很大，每次赋

13、值的代价就会很高。例如，输入为：(2，1)、(3，1)、(4，1)、(5，1)、(6，1)、(n，1)。显然，Y所在的集合越来越多，搜索集合及其应用；3.搜索集的实现和优化：2.搜索集链表的实现：2.快速实现上述简单实现并不理想。针对y可能相对较大的问题，可以很快产生一个聪明的想法：比较x和y所在集合的大小，然后做出选择，将较短的链表连接到较长的尾部，这样效果是一样的，但是成本肯定不会比原来的低。这就是快速实现的想法。您可以在节点中再设置一个字段编号，以记录此链接列表中的成员数。显然，这个数字可以记录在标题元素中。当合并两个表时，您只需要添加表的数量，所以维护起来非常方便。这种快速实现方法可以

14、称为加权启发式合并，其中权重指的是记录的数量。通过并行搜索集的实现和优化，以及并行搜索集链表的实现，证明了该方法的有效性。当有n个元素时，UNION上的成本上限(即重新分配的次数)为O(nlog2n)。考虑到一个固定的对象，当它的代表指针(头部)被更新时，X必须属于一个较小的集合。因此，在第一次更新X的代表指针后，结果集必须至少有2个元素。同样，在下一次更新后，X所在的集合必须至少有4个元素。继续下去，我们可以发现x的代表指针最多更新log2n次，因为在x所在的集合元素等于n之后，UNION操作不可能再次发生。因此，当总共有n个元素时，操作的总数不应超过nlog2n次。这确保了整个算法的复杂性

15、是理想的。联合搜索及其应用。联合搜索的实现和优化。实现链表的union搜索，合并两个集合的实现过程如下：UNION(x，y)x=FIND-SET(x)；y=FIND-SET(y)；如果x.numbery.number，则UNION(x，y)否则UNION(y，x)；链表的实现是一种非常可接受的算法，其效率是令人满意的。事实上，它的思想和数组完全一样，所以很少在实践中使用。联合搜索及其应用；3.联合搜索的实现与优化：3.联合搜索的树形实现：实现联合搜索的另一种方法是使用树。我们用一棵有根的树来代表一个集合。树中的每个节点都包含集合的一个成员，每个树代表一个集合。多个集合形成一个林状态，每个树的根

16、作为集合的代表，根节点的父节点指向它自己，而树上的其他节点使用父指针来表示它的从属关系。注意：同一棵树中的节点属于同一个集合。虽然它们在树中有父子节点关系，但这并不意味着它们之间有从属关系。树的指针仅用于连接集合中的元素。在并行搜索集中，对应于每个分离集的树称为分离集树。整个搜索集合也是一个单独的集合林。联合搜索及其应用；3.联合搜索的实现与优化：3.联合搜索的树形实现。下图显示了这种关系，包括分别由c和f表示的两组b、c、e、h、d、f和g。和搜索集及其应用；3.搜索集的实现和优化；3.搜索集的树实现。这种树形结构也可以简单地通过静态数组来实现，让px代表X元素所指向的父元素。MAKE-SE

17、T(x):px=x；FIND-SET(x):从x开始查找它的父亲，直到找到根。联合(x，y):只要一棵树的根指向另一棵树的根，它就成为一个子树。可以发现，元素之间的连接是通过指针实现的，与链表的实现相比，修改要少得多。然而，可以发现，尽管UNION(x，y)要简单得多，FIND-SET(x)需要从x开始，通过一个可能很长的路径来找到树的根。具体实现如下：(1)搜索集合及其应用；(3)实施和优化集合；(3)实现搜索集的树；(1)在分离集的森林中找到元素所属的集合，每个分离集的树对应一个集合。找到一个元素所属的集合就是找到对应于这个元素的节点所在的分离的集合树。分离集树的根节点的数量可以用来表示分离集树。这样，找到节点所在的分离集树意味着找到节点所在的分离集树的根节点。寻找树的根节点的方法非常简单，只需取树中的任何节点(我们也可以取我们正在寻找的节点)，沿着父节点的方向一直走到根：最初，取一个节点，到它的父