扩展域并查集学习笔记

并查集是个很有趣/常见/so esayの东西,不是吗?

今天,我要告诉你们,并不是这样的,虽然扩展域并查集比板子有趣多了,但未必(so ext{ }esay)

核心思想

它的核心思想嘛,如下:

1. fa[a]存储与a同类的
2. fa[a+1*n]存储与a发生第一类关系的
3. fa[a+2*n]存储与a发生第二类关系的
4. fa[a+3*n]存储与a发生第三类关系的
   ……

总之fa[a+i*n]表示与a发生第i类关系的(i为0即为同类)。

比如说: BOI2003 团伙这题,你就可以用fa[a]存储于a为朋友关系的;用fa[a+n]存储于a为敌人关系的。

详细可以看看我的题解这是一道典型的扩展域并查集的习题,大家可以去尝试。

推荐习题

1. BOI2003 团伙
2. 关押罪犯
3. 食物链

没错,这题也能用扩展域做,想一想吧!

最后

我这篇写的够良心了,网上很多都是直接讲题目,还没个思路的。

希望大家有所学习到!