并查集_解题技巧

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 898 阅读时长 ≈ 3 分钟

求连通块、集合个数

  • 能保证没有冗余的合并操作时

    正常情况下，初始时每个结点的祖先都是自己；若结点个数为tot，初始时则有tot个连通块

    每一次合并都会少一个连通块，就执行--tot；最终的连通块个数就等于tot

    比如P1536

  • 有冗余合并操作，但能固定祖先结点时

    例如P1892和P1621，通过固定祖先结点的方式，以\(O\left( n \right)\)的时间复杂度判断fa[i] == i即可得到连通块数

  • 上述情况都无法满足时

    先以\(O\left( n\log n \right)\)的时间复杂度寻找所有结点的祖先，再以\(O\left( n \right)\)的时间复杂度对祖先计数....

    还需要额外的\(O\left( n \right)\)的空间复杂度保存祖先....

    所以万不得已尽量别用该办法，考察并查集的题数据量都很大，很容易TLE

普通并查集

用法

并查集只有查询、合并两种操作！

其实是有删除操作的，参见Wiki

但实际复杂度高到天上去了....

并查集能在一张无向图中维护结点之间的连通性

这个“连通性”是可以通过结点之间的关系量化的

假设有一条规律，亲戚的亲戚也是我的亲戚

有A -> B，即A与B是亲戚；也有B -> C，显然能得到A -> C

练习题

  • P1551 并查集板子题
  • P1536 学会统计连通块
  • P1621 分类的思维
  • P1955 必刷的经典好题！强化后续的扩展域、边带权并查集理解
  • P2814 哈希表替代数组

作为优化手段/数据结构

  • P3535 并查集判环，并用反向建图实现贪心

  • P8686 优化搜索

  • P6121 反向建图实现并查集的结点删除

  • P8710 修改子结点，影响扩散至全集合

扩展域并查集（种类并查集）

用法

根据不同的关系属性，将数据拆分并重组为不同的集合

记得双向都要处理！因为a对b的关系，也同样有b对a

常见于求某一种关系的集合

举个例子，对于人而言，有“朋友”、“亲人”和“敌人”三种关系

现在要你求有几个“朋友”的集合

练习题

边带权并查集（带权并查集）

用法

扩展域并查集是根据关系将数据拆分重组成不同的集合

边带权并查集则是将关系映射为边权，从而能将不同的关系合并至同一集合

常见于判断所给条件是否满足前提

举个例子，对于人而言，有“朋友”、“亲人”和“敌人”三种关系

现有a、b二人，题目说他俩是亲人关系，要你辨真伪

你需要知道两件事：

  1. a和b有没有关系

    即希望a和b能够通过某种方式验证连通性，判断祖先是否一致

  2. a和b若有关系，符不符合题意

    即希望能记录a和b之间的关系

白话文来说，在边带权并查集中，任何两个结点都是连通的，代表这两个结点是“有关系的”

而两个结点之间的关系则通过它俩的边权记录，代表“是什么关系”

具体的设计思路，参考P2024

练习题