【算法-图论-并查集】 并查集简易攻略

由 联环己烷 发布

并查集,一种美丽而优秀的算法。

简单的来说,每个元素都可以有一个父亲,并且我们可以去查询它们的父亲和父亲的父亲。查到最后一个祖先,就可以确定这个元素在哪个集合里了。要合并两个集合时,也可以使两个集合的“祖先”们,一个当另一个的父亲。

当然,直接这么简单的并查集,可能会单次查询复杂度变成$O(n)$的,所以我们有两种优化方法。

1.路径压缩

查询时不断让当前节点的父亲指向最后那位祖先。这个均摊复杂度叫阿克曼函数,证明挺复杂的,要用势能(我也不懂),实际操作中可以把它当成常数。

int getf(int x) {return x==f[x]?x:f[x]=getf(f[x]);}

2.按秩合并

按秩合并是启发式合并的一种,具体来说,就是合并两个并查集时,最大深度小的并查集当儿子,大的当父亲。显然只有深度一致的并查集合并时,才会导致最大深度增大。

极限情况下,我们会不断地把深度一致的并查集合并,从而形成一棵类似完全二叉树的结构,不难发现此时深度是$log$级别的。

带权并查集

洛谷P2024 食物链

有$n$只动物分为A,B,C 3种,A吃B,B吃C,C吃A(骗鬼,生物老师明明说能量是单向流动的)。有$m$个说法,有两种格式:$X$和$Y$是同类或$X$吃$Y$。若一个说法与之前的说法冲突,则为假话,问有多少句假话?

如果因为一句判断,两个动物之间发生了关系,就将它们加入同一个并查集。

那么问题来了,怎么表示吃与被吃呢?

其实用距离就行了,节点与祖先的距离代表这个节点的动物是祖先那种动物沿着食物链往前走几步得到的,那么距离计算显然可以模3。这样若x和y在同一个并查集中,通过x和y与祖先的距离,就可以判断出x和y是怎么样的关系了。

注意,不能使用x和y之间的距离来解此题,而要使用它们分别与祖先的距离。想一想,为什么?

相似习题:poj1417,poj2912

并查集的其他运用

poj1456

超市要卖东西($n \leq 10000$),每个东西要花一天来卖,一天也最多卖一个东西,每个东西有一个价格和一个卖它的DDL(均$\leq 10000$),问超市最多可以赚多少钱?

显然我们会优先卖贵的东西。

用并查集,一个节点表示一天,并查集内的祖先为“该天及其更早的日子中,第一个没有安排卖东西的日子”。从价格高到低考虑每一个东西,尽量将其靠着DDL安排,安排好日子后,将这个日子与其更早一个的日子在并查集中合并。

可持久化并查集

利用可持久化数据结构(如主席树)实现的并查集,在此就不展开介绍。

Litble曾经在考前打洛谷P3402板子,并因此在NOI2018以极快的速度切掉了Day1的“归程”,从而成功因为不会后缀自动机与金牌失之交臂。因此啊,大家一定要学好后缀自动机学习可持久化并查集。


暂无评论

发表评论


京公网安备 11010802033049号