首页 > 代码库 > 小结:并查集

小结:并查集

复杂度:

O(n*α(n)) 其中α(x),对于x=宇宙中原子数之和,α(x)不大于4 。(对于nocow里的复杂度我也是醉了)

概要:

并查集就是一个数组和一行话。

应用:

图的连通、集合操作、生成树的合并等

技巧及注意:

并查集是个好东西。

维护区间+前缀和:对于一些连续的区间,我们要判断这些区间是否合法,带修改。这种题我们可以考虑并查集来维护区间,用前缀和维护信息,而在并查集按秩合并的时候,一定要注意合并前和合并后如何维护信息,比如这题【BZOJ】1202: [HNOI2005]狡猾的商人(并查集+前缀和)就用到了当合并时,只需加上原父亲的前缀和即可(因为最后会被合并到一个新根),注意细节就好,一定要画图理解!

维护连通:当对于一种树只需要判断是否连通,带link-cut操作时,乍一看好像是lct,但是仔细想想,又不需要维护区间信息,那么我们直接用并查集的特殊性,实现link-cut操作,例题:【BZOJ】2049: [Sdoi2008]Cave 洞穴勘测(lct/并查集)

小结:并查集