华师一附中OI组

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

作者: admin 时间: 2018-5-11 17:15
标题: 并查集专题
并查集是数据结构里面一个很基本的内容，一般的做法是：
1、若i和j被放在同一集合，则f(i)=F(j)。
2、查询i和j是否在一个集合只要判断F(i)==F(j)。
函数F(i)是并查集程序的精华，小规模可以返回标号最小的祖先、集合规模最大的那个祖先等等，但是最科学的还是路径压缩：
在找i的祖先的过程中，假设i的爸爸是j，j的爸爸是k，k的爸爸是l，l的爸爸是自己，那么找的过程中顺便把ijk的爸爸都变成l，这样在查找的过程中就比较快。

并查集是一种树型的数据结构，一般用于处理一些不相交集合（Disjoint Sets）的合并及查询问题，其基本目的就是将两个集合进行合并和判断两个元素是否在同一个集合里面。
对于普通的并查集我们一般分为三个部分——初始化，查找，合并。
程序中一般用数组f(i)表示i元素的祖先，函数F(i)用来求i的祖先；
1、初始化：把每个点所在集合初始化为其自身（即每个元素单独构成一个集合，其父结点是其本身）。
2、查找：查找元素所在的集合，即根节点。
3、合并：将两个元素所在的集合合并为一个集合
这个是并查集的重点：当我们想对两个元素进行合并时，那么必然时它们之间存在某种关系。在进行合并前，我们首先需要进行一次判断，判断这两个元素是否已经在同一个集合了，若是已经在同一个集合则没必要重复合并，若不是在同一个集合则需要合并，通常我们判断两个元素是否在同一个集合是通过查找操作查找这两个元素的祖先，若两个元素的祖先一致则是在同一集合，反之不然。合并的时候要考虑合并的策略，若将元素个数少的集合合并到多的集合可能改动会比较小，或者，讲离根节点比较远的合并到比较近的。但是常用的一般是路径压缩：当我们在寻找祖宗节点时，会遇到两种情况

第一种情况：                                                                                        第二种情况：

显然，当我们遇到的是第一种情况的时候，其父节点就是其祖宗节点（根节点），这种情况路径压缩显然是很没有用处的，不过当我们遇到第二种情况的时候，我们找寻的是x的祖宗节点（根节点），在找寻的过程中，我们发现x有许多的长辈，这些长辈的祖宗节点和x的祖宗节点是同一个，那么我们为了节省以后找这些长辈节点的祖宗节点的时间，我们直接在找x的祖宗节点的同时顺带找到这些长辈节点的祖宗节点（因为他们的祖宗节点是同一个），在进行完这些操作（路径压缩）之后，上面的第二个图就变成了下面这个图了。

这样，在查找祖先的过程中顺便将路上的每个节点的祖先也都给改了，整个数的深度就得到了大大的降低。

1、P3367 【模板】并查集  http://hsyit.cn/forum.php?mod=viewthread&tid=36253
2、P1551 亲戚 http://hsyit.cn/forum.php?mod=viewthread&tid=36019
3、P2078 朋友 http://hsyit.cn/forum.php?mod=viewthread&tid=36254
4、P2342 叠积木  http://hsyit.cn/forum.php?mod=viewthread&tid=36255
5、P3958 NOIP2017 奶酪  http://hsyit.cn/forum.php?mod=viewthread&tid=36090
6、P1197 [JSOI2008]星球大战  http://hsyit.cn/forum.php?mod=viewthread&tid=36389

作者: admin 时间: 2019-4-16 16:42
简单的并查集只需要记录某个元素的祖先，有的时候我们除了记录祖先之外可能还需要记录一些其他的信息，比如，总和，类别等等，这样的叫做带权并查集，
1、How Many Answers Are Wrong http://hsyit.cn/forum.php?mod=viewthread&tid=69295
银河英雄传说

并查集有个变形叫种类并查集，用于处理敌人的敌人是朋友这类分种类讨论的问题，比较典型的是1、P2024 食物链 http://hsyit.cn/forum.php?mod=viewthread&tid=36020
2、关押最烦

欢迎光临华师一附中OI组 (http://hsyit.cn/)