【模板】并查集

题目

洛谷P3367并查集

题解

并查集是一种支持合并与查询的数据结构。合并:如果要将元素a,b所在的两个集合合并,则将a所在集合的根节点作为b所在集合的根节点的子节点。一棵树上的所有节点属于同一个集合,根节点没有特殊意义,只是代表这个集合。 查询:如果想知道某个元素在哪个集合,就不断访问它的父节点,直到根节点。

[优化方法] 路径压缩:在查询过程中,将一路上的节点的父节点都改为根节点,减少以后查询的时间。 按秩合并:尽量减小树的深度,使得查询速度变快。但在路径压缩的前提下,这个优化的效果不明显。将深度小的数并到深度大的树上,使合并后的数深度小。也可以将深度改为集合内的元素个数,更加方便和实用。假设一个集合当前有x个元素,则将根节点的父节点设为 -x。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月3日 下午9:00

【小白解析】
此题解结构简约但不简单。乍一看似乎缺少对fa[]数组的初始化,实际上find操作既是对每一个节点初始化:每一次查询数据,若数据x所在的集合为单元素集合,fa[x]==-1,返回其本身x;若fa[x]>0,即x的集合中还有其他元素,考虑unite所做的操作:

  • 先考察fa[r1]与fa[r2]的大小——此时的两个数组成员应该都是负整数;其绝对值代表元素数量(具体原因是?表达式后的fa[r2]+=fa[r1](或者相反)操作)。若r1所在的分支较短(绝对值小,负数更大),则将r1的分支长度加在r2上,随后将r2设为r1的父节点(fa[r1]=r2)。反之则操作相反。

回到正题。此时若x的情况尚未被更新,则fa[x]应当为x最近的父节点值。此时不断通过find(fa[x])来查询其父节点的fa[]情况(例:沿用上述情况。若find(r1),则会执行find(r2)。r2<0,故返回r2值。)。当fa[]为负时,得到真正的起源节点;此时将节点赋值给考察过的每一个父节点(fa[x]=find(fa[x])),完成更新。
*((括号) (?)) ((咱) ((向来)(是)) (有多少(加)多少)(的))(嚣张)