什么是并查集?
并查集就是一个“反复查询内容所在的集合”的数据结构。
当然,这样理解好像并不是很清楚,那么我们来画个图吧。
首先我们有一个森林。每颗树只有一个根节点
然后呢我们要进行一个“操作”,让1所在的树与2所在的树划到一起
最后我们把第2所在的树与第3所在的树划在一起 (扔到一起)
最后可能会查询1与3是否在一个集合。其实就是询问1与3是否在一棵树上。从图上观察,很容易即可发现他们在同一棵树上。
并查集的维护
提前声明 : 并查集的实现方法其实只有一种。但是存入数组的方法并不一样。这里统一使用负数判断法。意思就是越小代表该树节点个数越大。(example: -1代表这棵树拥有1个子节点,-2代表拥有2个,$-n$即拥有$n$个子节点。一开始由于都有一个,所以所有值均为-1)我们暂且叫这个数组t.
合并 : 找到x,y的根节点。看谁的节点少,少的节点接到多的后面。
查询 : 查看x与y是否为同一个根。
并查集的优化
众所周知,OI考试出题的都是毒瘤的出题人!他们最爱干什么(指在树上)?把你的树卡成一条链!一条链的查询时间复杂度直接就能卡成$$O(n)$$!那么我们怎么优化呢。有一个好方法,路径压缩。方法就是将所有链上的节点的父亲设为其根节点。即设tree $\left[a_{i} \sim n\right]$. father $=$ root.具体实践可能不同。当然有更优秀的方法,在我们查询根节点时设置所有的子节点即可。
并查集的时间复杂度分析
路径压缩后的图应该是任意节点的父亲节点均为根节点。
所以查询时间复杂度为$O(log n)$后面的时间复杂度不超过该事件复杂度。
合并事件复杂度应为$O(log n)$后不会超过该时间复杂度
不使用路径压缩的话,最坏时间复杂度为$O(n)$(一条链)