并查集及其应用PPT课件.ppt

并查集及其应用 一 引例例一 亲戚 relation 问题描述 或许你并不知道 你的某个朋友是你的亲戚 他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子 如果能得到完整的家谱 判断两个人是否亲戚应该是可行的 但如果两个人的最近公共祖先与他们相隔好几代 使得家谱十分庞大 那么检验亲戚关系实非人力所能及 在这种情况下 最好的帮手就是计算机 为了将问题简化 你将得到一些亲戚关系的信息 如Marry和Tom是亲戚 Tom和Ben是亲戚 等等 从这些信息中 你可以推出Marry和Ben是亲戚 请写一个程序 对于我们的关于亲戚关系的提问 以最快的速度给出答案 1 并查集及其应用 输入由两部分组成 第一部分以N M开始 N为问题涉及的人的个数 1 N 20000 这些人的编号为1 2 3 N 下面有M行 1 M 1000000 每行有两个数ai bi 表示已知ai和bi是亲戚 第二部分以Q开始 以下Q行有Q个询问 1 Q 1000000 每行为ci di 表示询问ci和di是否为亲戚 输出 对于每个询问ci di 输出一行 若ci和di为亲戚 则输出 Yes 否则输出 No 2 并查集及其应用 输入样例 relation in 1072457138912562333471089 输出样例 relation out YesNoYes 3 并查集及其应用 问题分析 将每个人抽象成为一个点 数据给出M个边的关系 两个人是亲戚的时候两点间有一条边 很自然的就得到了一个N个顶点M条边的图论模型 注意到传递关系 在图中一个连通块中的任意点之间都是亲戚 对于最后的Q个提问 即判断所提问的两个顶点是否在同一个连通块中 用传统的思路 马上可以反应过来 对于输入的N个点M条边 找出连通块 然后进行判断 但这种实现思路首先必须保存M条边 然后再进行普通的遍历算法 不管是从空间还是时间上看 效率都不高 再进一步考虑 如果把题目的要求改一改 对于边和提问相间输入 即把题目改成 4 并查集及其应用 第一行是N M N为问题涉及的人的个数 1 N 20000 这些人的编号为1 2 3 N 下面有M行 1 M 2000000 每行有三个数ki ai bi ai和bi表示两个元素 ki为0或1 ki为1时表示这是一条边的信息 即a表示i和bi是亲戚关系 ki为0时表示这是一个提问 要你根据此行以前所得到的信息 判断ai和bi是否是亲戚 对于每条提问回答Yes或者No 这个问题比原问题更复杂些 需要在任何时候回答提问的两个人的关系 并且对于信息提示还要能立即合并两个连通块 采用连通图思想显然在实现上就有所困难 因为要实时地表示人与人之间的关系 5 并查集及其应用 用集合的思路 对于每个人建立一个集合 开始的时候集合元素是这个人本身 表示开始时不知道任何人是他的亲戚 以后每次给出一个亲戚关系时 就将两个集合合并 这样实时地得到了在当前状态下的集合关系 如果有提问 即在当前得到的结果中看两元素是否属于同一集合 对于样例数据的解释如下图 6 并查集及其应用 输入关系分离集合初始状态 1 2 3 4 5 6 7 8 9 10 2 4 1 2 4 3 5 6 7 8 9 10 5 7 1 2 4 3 5 7 6 8 9 10 1 3 1 3 2 4 5 7 6 8 9 10 8 9 1 3 2 4 5 7 6 8 9 10 1 2 1 2 3 4 5 7 6 8 9 10 5 6 1 2 3 4 5 6 7 8 9 10 2 3 1 2 3 4 5 6 7 8 9 10 7 并查集及其应用 用集合的思路 对于每个人建立一个集合 开始的时候集合元素是这个人本身 表示开始时不知道任何人是他的亲戚 以后每次给出一个亲戚关系时 就将两个集合合并 这样实时地得到了在当前状态下的集合关系 如果有提问 即在当前得到的结果中看两元素是否属于同一集合 对于样例数据的解释如下图 由上图可以看出 操作是在集合的基础上进行的 没有必要保存所有的边 而且每一步得到的划分方式是动态的 如何来实现以上的算法思想呢 我们就用到并查集 8 并查集及其应用 二 并查集的基本思想 1 什么叫并查集并查集 union findset 是一种用于分离集合操作的抽象数据类型 它所处理的是 集合 之间的关系 即动态地维护和处理集合元素之间复杂的关系 当给出两个元素的一个无序对 a b 时 需要快速 合并 a和b分别所在的集合 这其间需要反复 查找 某元素所在的集合 并 查 和 集 三字由此而来 在这种数据类型中 n个不同的元素被分为若干组 每组是一个集合 这种集合叫做分离集合 disjointset 并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并 9 并查集及其应用 二 并查集的基本思想 例如 有这样的问题 初始时n个元素分属不同的n个集合 通过不断的给出元素间的联系 要求实时的统计元素间的关系 是否存在直接或间接的联系 这时就有了并查集的用武之地了 元素间是否有联系 只要判断两个元素是否属于同一个集合 而给出元素间的联系 建立这种联系 则只需合并两个元素各自所属的集合 这些操作都是并查集所提供的 并查集本身不具有结构 必须借助一定的数据结构以得到支持和实现 数据结构的选择是一个重要的环节 选择不同的数据结构可能会在查找和合并的操作效率上有很大的差别 但操作实现都比较简单高效 并查集的数据结构实现方法很多 一般用的比较多的是 数组实现 链表实现和树实现 10 并查集及其应用 二 并查集的基本思想 并查集的数据结构记录了一组分离的动态集合S S1 S2 Sk 每个集合通过一个 代表 加以识别 代表即该元素中的某个元素 哪一个成员被选做代表是无所谓的 重要的是 如果求某一动态集合的代表两次 且在两次请求间不修改集合 则两次得到的答案应该是相同的 动态集合中的每一元素是由一个对象来表示的 设x表示一个对象 并查集的实现需要支持如下操作 2 并查集支持的操作 11 并查集及其应用 二 并查集的基本思想 2 并查集支持的操作 MAKE SET x 建立一个新的集合 其仅有的成员 同时就是代表 是x 由于各集合是分离的 要求x没有在其它集合中出现过 UNION x y 将包含x和y的动态集合 例如Sx和Sy 合并为一个新的集合 假定在此操作前这两个集合是分离的 结果的集合代表是Sx Sy的某个成员 一般来说 在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表 此后 由新的集合S代替了原来的Sx和Sy FIND SET x 返回一个指向包含x的集合的代表 12 并查集及其应用 三 并查集的实现及优化 1 并查集的数组实现 实现并查集的最简单的方法是用数组记录每个元素所属的集合的编号 查找元素所属的集合时 只需读出数组中记录的该元素所属集合的编号即可 时间复杂度为O 1 合并两元素各自所属的集合时 需要将数组中属于其中一个集合的元素所对应的数组元素值全部改为另一个集合的编号值 时间复杂度为O n 由于实现简单 所以实际使用的很多 以上的数组实现虽然很方便 但是合并的代价太大 在最坏情况下 所有集合合并成一个集合的总代价可以达到O n2 13 并查集及其应用 三 并查集的实现及优化 2 并查集的链表实现 我们需要用一定的数据结构来组织动态的集合 同一集合中的所有元素应该是联系在一起的 一种比较简单的想法是用链表来实现 每个集合对应一个链表 它有一个表头 每一个元素有一个指针指向表头 表明了它所属的类 另有一个指针指向它的下一个元素 同时为了方便实现 再设一个指针last表示链表中的最后一个元素 表尾 可以选择静态数组 一般来说这种问题处理的对象都是连续整数 可以用下标来对应元素 来实现 定义一个记录为 typenode recordhead next last integer end varS array 1 maxn ofnode 14 并查集及其应用 三 并查集的实现及优化 2 并查集的链表实现 可以得到MAKE SET和FIND SET的实现为 MAKE SET x S x head x S x next 0 FIND SET x returnS x head 两个过程的时间复杂度都为O 1 注意到我们采用链表以后 当有两个元素 x y FIND SET x FIND SET y 时 两者对应不同的集合 需要将两个链表合并 做法是将一个表的表头直接接到另一个表的表尾 这步操作很简单 但势必造成修改后需要把接上去的那个表的所有head值修改 这需要线性的赋值操作 其复杂度与选择接在尾部的链表长度成正比 15 并查集及其应用 三 并查集的实现及优化 2 并查集的链表实现 现在讨论UNION x y 的实现 假设UNION x y 的参数是有序的 即把y属于的集合合并到x的集合 有两种实现方法 1 简单实现不考虑任何因素 出现FIND SET x FIND SET y 时 直接将y的表头接到x的尾 同时将y中所在集合元素所有元素的head设为FIND SET x 同时x的表尾也应该设为原y的表尾 注意last指针其实只要在表头结点中记录即可 因为每一次查到FIND SET x 都可以得到表头元素 而链表中其他元素重新记录last是无意义的 考虑输入数据的特殊性 我们总是把y接到x里去 那么如果y所在的集合非常大 每次赋值的代价就会非常高 比如出现输入为 2 1 3 1 4 1 5 1 6 1 n 1 显然y所在的集合越来越庞大 对于这种方法最坏情况下时间复杂度为O n 2 16 并查集及其应用 三 并查集的实现及优化 2 并查集的链表实现 2 快速实现上述简单实现非常不理想 针对y可能比较大的这个问题 可以很快产生一个聪明的想法 不妨比较x和y所在集合的大小 从而作出选择 把较短的链表接在较长的尾部 这样效果是一样的 但耗费肯定不比原来差 这就是快速实现的思路 可以在node里多设一个域number 用来记录此条链表中成员的个数 显然number记录在表头元素中即可 将两表合并的时候 只要将表的number相加 因此维护起来是非常方便的 这种快速实现的方法可以称为加权启发式合并 这里的权就是指所记录的number 17 并查集及其应用 三 并查集的实现及优化 2 并查集的链表实现 可以证明这种方法的效率 当有n个元素时 在UNION上的花费 即重新赋值的次数 的上界是O nlog2n 考虑一个固定的对象x 当x的代表指针 head 被更新时 x必是属于一个较小的集合 因此 x的代表指针第一次更新后 结果集合必然至少有2个元素 类似的 下一次更新后 x所在的集合至少有4个元素 继续下去 可以发现 x的代表指针最多被更新log2n次 因为当x所在集合元素已经等于n以后 不可能再发生UNION操作 所以 总共有n个元素时 操作的总次数不超过nlog2n次 这就保证了整个算法的复杂度是理想的 18 并查集及其应用 三 并查集的实现及优化 2 并查集的链表实现 合并两个集合时的实现过程如下 UNION x y x FIND SET x y FIND SET y ifx number y numberthenUNION x y elseUNION y x 并查集的链表实现是一种非常容易接受的算法 并且它的效率也是令人满意的 其实它的思路和数组完全一样 所以实际使用较少 19 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 实现并查集的另一种方法是利用树 我们用有根树来表示集合 树中的每个节点包含集合的一个成员 每棵树表示一个集合 多个集合形成森林态 以每棵树的树根作为集合的代表 并且根结点的父结点指向其自身 树上的其他结点都用一个父指针表示它的附属关系 注意 在同一棵树中的结点属于同一个集合 虽然它们在树中存在父子结点关系 但并不意味着它们之间存在从属关系 树的指针起的只是联系集合中元素的作用 在并查集中 每个分离集合对应的一棵树 称为分离集合树 整个并查集也就是一棵分离集合森林 20 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 下图表示了这种关系 其包含两个集合 b c e h d f g 分别以c和f作为代表 21 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 这种树结构也可以简单地用静态数组实现 设p x 表示x元素所指向的父亲 MAKE SET x p x x FIND SET x 要从x开始 向上寻找它的父亲 直到找到根为止 UNION x y 只要使一棵树的根指向另一棵树的根 即成为一棵子树 可以发现 元素之间的联系是靠指针来实现的 与链表的实现相比 所需要进行的修改少了许多 但可以发现 UNION x y 虽然是简便了许多 但是FIND SET x 则需要从x开始 经过一条可能比较长的路径 才能找到树根 具体实现如下 22 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 1 查找一个元素所属的集合在分离集合森林中 每一棵分离集合树对应一个集合 要查找某一元素所属的集合 就是要找这个元素对应的结点所在的分离集合树 不妨以分离集合树的根结点的编号来表示这个分离集合树 这样 查找一个结点所在的分离集合树 也就是查找该结点所在分离集合树的根结点了 查找树的根结点的方法很简单 只需任取树中一结点 不妨就取我们要查找的那个结点 沿父结点方向一直往树根走 初始时 取一个结点 走到它的父结点 然后以父结点为基点 走到父结点的父结点 直至走到一个没有父结点的结点为止 这个结点就是树的根结点 23 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 1 查找一个元素所属的集合下图描述了查找一个结点的过程 黑色结点为当前查找结点 查找算法的复杂度取决于查找结点的深度 假设查找结点的深度为h 则算法的时间复杂度为O h 24 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 2 两个元素各自所属的集合的合并 在分离集合森林中 分离集合是用分离集合树来表示的 要合并两个元素各自所属的集合 也就是合并两元素所对应的两个结点各自所在的分离集合树 现在的问题就是如何合并两棵分离集合树 考虑到在分离集合森林中 只要结点属于同一棵树 即被视为在同一个集合中 而不管具体是如何相连的 那么 我们只需简单的将一棵分离集合树作为另一棵的子树 即可使两棵树合并为一棵 如下图 描述的是将两棵分离集合树D1和D2合并的过程 D1作为D2的根结点的一棵子树 25 2020 2 5 26 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 2 两个元素各自所属的集合的合并 要完成上述合并 首先要找到两棵分离集合树的根结点 这可以通过调用两次查找算法得到 得到根结点后 只需改变其中一个根结点 令它的父结点为另一个根结点即可 代价为O 1 因此 整个合并算法的复杂度主要在查找根结点部分 为O h 27 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 3 优化查找与合并算法前面提到 分离集合森林的查找与合并的时间复杂度都是O h 也就是说 查找与合并的时间复杂度主要取决于树的深度 就平均情况而言 树的深度应该在logn的数量级 n为结点个数 所以分离集合森林查找与合并的平均时间复杂度为O logn 但是 在最坏情况下 一棵树的深度可能达到n 如右图 这时的查找与合并的时间复杂度都达到了O n 这是我们不愿意看到的 因此必须想方设法避免出现这种情况 为了提高效率 可以考虑在UNION x y 和FIND SET x 上作一些文章 28 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 3 优化查找与合并算法 优化合并过程分析一下前面那棵深度为n的分离集合树的形成过程 可以看出 这是合并不当的后果 当合并右图的两棵分离集合树 A B 时 显然将B树作为A树根结点的子树得到的树比较平衡 如下图中的C树 D树为A树作为B树根结点的子树得到的树 29 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 3 优化查找与合并算法 优化合并过程 一棵较平衡的树拥有比较低的深度 查找和合并的复杂度也就相应得较低 因此 如果两棵分离集合树A和B 深度分别为hA和hB 则若hA hB 应将B树作为A树的子树 否则 将A树作为B树的子树 总之 总是深度较小的分离集合树作为子树 得到的新的分离集合树C的深度hC 以B树作A树的子树为例 hC max hA hB 1 这样合并得到的分离集合树 其深度不会超过logn 是一个比较平衡的树 因此 查找与合并的时间复杂度也就稳定在O logn 了 30 并查集及其应用 三 并查集的实现及优化 3 并查集的树实现 3 优化查找与合并算法 优化查找过程对于查找过程有两个方面的启发式方法都很有效 分别是按秩合并和路径压缩优化 31 并查集及其应用 A 按秩合并可以联系一下链表的优化 我们是选择比较小的一个集合归并到大的集合里去 对于有根树的结构 很类似地 也可以记录树上的节点数 将较小的树的根指向较大的树 但是有根树的结构又有非常特殊的地方 它的一个节点下面可能挂有很多子树 从前面分析也可以看出 主要的时间花在了FIND SET x 上 只要使得树中不存在一条偏长的路径 即使得各条路径的长度都比较平均了 那么算法就不会出现特别退化的情况 对每个结点 用一个秩 rank 来近似子树大小对数 同时它也是该节点高度的一个上界 进行UNION的时候 只要让具有较小秩的根指向具有较大秩的根 如果两根的秩相等 只要使其中一个根指向另一个 同时秩应当增加1 这十分类似于统计节点个数 但这里统计的是树的深度 32 并查集及其应用 B 路径压缩优化方法在分离集合森林中 分离集合是用分离集合树来表示的 分离集合树是用来联系集合中的元素的 只要同一集合中的元素在同一棵树上 不管它们在树中是如何被联系的 都满足分离集合树的要求 如下图 这两棵分离集合树是等价的 因为它们所包含的元素相同 显然 右边那棵树比较 优秀 因为它具有比较低的深度 相应的 查找与合并的时间复杂度也较低 那么 我们就应该使分离集合树尽量向右树的形式靠拢 33 并查集及其应用 在查找一个结点所在树的根结点的过程中 要经过一条从待查结点到根结点的路径 我们不妨就让这些路径上的结点直接指向根结点 作为根结点的子结点 这样 这些路径上的结点仍在分离集合中 整棵树仍然满足分离集合树的要求 而路径上的结点的深度无疑降低了 这些点及其子树上的结点的查找复杂度大大降低 如下图 描述了在一棵分离集合树查找结点7的前后所呈现出的结构 34 并查集及其应用 这种改变结点所指方向以降低结点深度 从而缩短查找路径长度的方法 叫做路径压缩 实现路径压缩的最简单的方法是在查找从待查结点到根结点的路径时走两遍 第一遍找到树的根结点 第二遍改变路径上结点指向根结点 使它们的父结点为根结点 使用路径压缩大大提高了查找算法的效率 如果将带路径压缩的查找算法与优化过的合并算法联合使用 则可以证明 n次查找最多需要用O n n 时间 n 是单变量阿克曼函数的逆函数 它是一个增长速度比logn慢的多但又不是常数的函数 在一般情况下 n 4 可以当作常数看 这种方法是在FIND SET x 过程中作一些改进 设想 从x到它的根 我们必须经过一条路径 显然这条路径上的所有的根与x的根是同一个根 那么不妨在得到结果的同时 顺便把这条路上全部节点的根都改成x的根 也就是说 对这些节点进行了分散 其结果是 下一次如果再有这条路上的点进行FIND SET x 时 只要经过一步就可以找到根 可以认为是x顺便帮了帮大家的忙 把好处带给了大家 因此其它节点以后都省事了 35 并查集及其应用 FIND SET x 36 并查集及其应用 使用这两种方法优化后的代码 MAKE SET x p x x rank x 0 UNION x y x FIND SET x y FIND SET Y ifrank x rank y thenp y xelse p x yifrank x rank y thenrank y rank y 1 FIND SET x ifxp x thenp x FIND SET p x returnp x 37 并查集及其应用 可以看到FIND SET x 是一个递归的过程 它的实现非常简洁 同时我们的方法也可以保证递归深度不会很深 事实上只要使用这两种方法中的任何一种 算法的效率都会大大提高 当两种方法结合起来以后 效率更高 几乎可以接近n的线性复杂度 四 引例的实现程序1 数组实现 relation1 pas 2 链表实现 relation2 pas 3 树实现 relation3 pas 38 并查集及其应用 五 应用举例并查集可以作为一些复杂问题的一部分 甚至有一些特殊的应用 这里只举一些最浅显的应用例子 例二 食物链 NOI2001 eat 问题描述 动物王国中有三类动物A B C 这三类动物的食物链构成了有趣的环形 A吃B B吃C C吃A 现有N个动物 以1 N编号 每个动物都是A B C中的一种 但是我们并不知道它到底是哪一种 有人用两种说法对这N个动物所构成的食物链关系进行描述 第一种说法是 1XY 表示X和Y是同类 第二种说法是 2XY 表示X吃Y 此人对N个动物 用上述两种说法 一句接一句的说出K句话 这K句话有的是真的 有的是假的 39 并查集及其应用 你从头开始一句一句的读入这K句话 当你读到的话满足下列三条之一时 这句话就是假的 否则就是真的 1 当前的话与前面的某些真的话冲突 2 当前的话中X或Y比N大 3 当前的话表示X吃X 你的任务是根据给定的N 1 N 50 000 和K个条件 0 K 100 000 输出假话的总数 输入文件 eat in 第一行是两个整数N和K 以一个空格分隔 以下K行每行是三个正整数D X Y 之间用一个空格隔开 其中D表示说法的种类 若D 1 X和Y是同类 若D 2 X吃Y 输出文件 eat out 一个整数 表示假话的数目 40 并查集及其应用 输入样例 100711011 假212 真223 真233 假113 假231 真155 真 输出样例 3 41 并查集及其应用 算法分析 本题和亲戚问题其实是差不多的 两者的数学模型已经不能再相似了 它就相当于例一中提出的亲戚问题的第2版 即边合并还需要边判断 本题的难点恐怕在于两个点的关系不仅是同集合的关系 还涉及到在同一集合中处于怎样的捕食关系 显然在同一个集合中还需要对各种动物进行标号 用0 1 2对每种动物染色 如下图所示 如果两个动物x和y同类 则color x color y 如果x吃y 那么 color x 1 mod3 color y 42 并查集及其应用 这时对两个集合UNION x y 进行合并时就需要做更多的工作 假定x集合颜色不变 那么要把y集合并到x集合中 y集合的每个元素只要全部相应增加某一个增值d 就可以把x y统一起来了 例如x和y属于同类 而color x 2 color y 1 y集合中所有元素的颜色都增加1 mod3 两集合元素的颜色就统一了 考虑该算法的实现 前面的讨论中 可知用有根树来实现效率是非常高的 但高效的方法未必好用 比如对于此题 如果采用有根树的直接实现 由于元素之间存在染色的转换 那么维护有根树时 树内动物之间的关系无法及时明确 事实上本题可以简单地采用链表实现的方法 前面已经说了 只要将y里面的元素进行一下调整 链表实现中本来就需要对y集合里每个节点的代表指针进行调整 因此此步改变只需要在原算法中稍作添加 不需要更进一步的复杂讨论了 43 并查集及其应用 例三 求无向图的连通分量这个问题其实在例一中已经提过了 这里再单独提出来强调一下 因为求无向图连通分量是个非常常用的算法 通过并查集可以使得空间上省去对边的保存 同时时间效率又是很高的 需要特别指出的是 如果用链表来实现的话 最后任何在同一个集合 即连通块 中的元素 其代表指针的值都是相等的 而采用有根树来实现的话 算法结束后 留下的依然是树的关系 因此如果希望每个元素都指向它的根的话 还需要对每个节点进行一次FIND SET操作 这样每个节点的父节点都是代表此集合的节点 在某些统计问题中 往往需要这样做 而从另一方面讲 有根树的实现 如果忽略 按秩合并 这一优化 时间效率依然是很高的 但可以省去RANK这个线性空间的保存 因此在某些时候如果内存紧张的话 是可以以牺牲时间来换取空间的 44 并查集及其应用 例四 Kruskal最小生成树算法此经典算法的思想是将树上的边按照权排序 然后从小到大分析每一条边 如果选到一条边e v1 v2 且v1和v2不在一个连通块中 就将e作为最小生成树的一条边 否则忽略e 这其中明显就包