概述
并查集($Disjoint\ Set\ Union$),是一种可以动态维护若干个不重叠的集合,并支持合并与查找的数据结构。详细地说,并查集包括如下两个基本操作:$1.$查询一个元素属于哪个集合;$2.$合并两个集合。优化方法有路径压缩与按秩合并,一般只需路径压缩。
以下典型题只考察了并查集的基本操作,在进一步深入前,需要弄清这几题。
合并集合 亲戚
功能各异的并查集
图论中的并查集
整个并查集实际上是一个森林(若干棵树),而每一棵树就是一个连通块。因此许多与连通块,连通性有关的题目都可以用并查集来解决。除此之外,很多判环问题,找奇数环偶数环问题,也应该想到并查集试试。
相关题有: 连通块中点的数量 信息中断 格子游戏 Codeforces 1702E.Split Into Two Sets
程序自动分析 UVA 1665.Islands
边带权并查集
并查集实际上是由若干棵树构成的森林,我们可以在树中的每条边上记录一个权值,即维护一个数组$d$,用$d[x]$保存节点$x$到父结点$p[x]$之间的边权。在每次路径压缩后,每个访问过的节点都会直接指向树根,如果我们同时更新这些节点的$d$值,就可以利用路径压缩过程来统计每个节点到树根之间路径上的一些信息。这就是所谓的边带权并查集。带权并查集常用于解决一些有关”关系”的题目。
扩展域并查集(种类并查集)
个人认为扩展域并查集在思维量上要比带权并查集小得多,基本不用思考细节。其核心思想就是把拆点,数组的大小根据题意翻几倍。感觉像奇偶游戏、食物链这样的题,运用扩展域即可。带权并查集更适合处理银河英雄传说(扩展域做不了此题)这样的题和空间限制较严格的题。