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

今天,我要告诉你们,并不是这样的,虽然扩展域并查集比板子有趣多了,但未必\(so\text{ }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即为同类)。

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

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

推荐习题

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

最后

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

希望大家有所学习到!