Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

有关并查集的一点知识

初印象

CCF将并查集设置为高级数据结构
感觉这个东西挺好玩的 直接能合并

什么是并查集

并查集是一棵树 对于这棵树我们用一个fa[i]记录在这棵树上面i的父亲是谁
所以说用这个我们可以维护一些关系
两个东西之间的联系我们都可以用并查集维护

算法复杂度

空间复杂度为O(N),建立一个集合的时间复杂度为O(1),N次合并M查找的时间复杂度为O(M Alpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内(人类目前观测到的宇宙范围估算有10的80次方个原子,这小于前面所说的范围)这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是线性的。具体复杂度分析过程见参考资料(3)。
大概跟阿克曼函数有点关系 具体的不会证明

算法原理

  • getroot(x)得到x这个节点的爸爸
  • union(x,y) 把这两个并查集(也就是两棵树)合并起来

算法优化

常见的优化有两种

1.压缩路径

根据上面的描述 我们发现对于一棵树中的某一个节点
如果它的深度很大 但是我们想要找的 跟它有联系的那个节点的深度很小
那么我们就要进行很多次getroot操作 这样的话时间复杂度线性就不存在了
这个时候我们进行处理 毕竟你在这一棵树里面相当于我们说在同一个并查集中
它们的代表元素fa[i]都是相同的
所以深度显得无所谓
这样的话我们可以采用如下处理方式
寻找祖先时,我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度。为了避免这种情况,我们需对路径进行压缩,即当我们经过”递推”找到祖先节点后,”回溯”的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了,如下图所示。可见,路径压缩方便了以后的查找

2.按秩合并

有点像启发式合并
union的时候把小的往大的上面合并就行了

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏