什么是并查集？
并查集就是一个“反复查询内容所在的集合”的数据结构。
当然，这样理解好像并不是很清楚，那么我们来画个图吧。
首先我们有一个森林。每颗树只有一个根节点
然后呢我们要进行一个“操作”，让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)$(一条链)