并查集
并查集是用来查找和合并集合关系的
这个集合必须是不交集
支持查找和合并两种操作，修改后可以支持删除单个元素并分离集合。
使用动态开点线段树还可以实现可持久化并查集
来自 https://oi-wiki.org/ds/dsu/
并查集类似于树，普通并查集是无向的，但是加权并查集是可以做到有向的，详见NOI2001食物链
查找操作：查找两个元素是否在同一集合
假设有一个集合，元素是{1,2,3}
还有一个集合元素是{4,5,6}
现在查找2和4在不在同一个集合，则需要枚举2所在或4所在集合所有元素直到找到4或到最后也没有4
太慢了，有一个更好的方法，如果我们随便选一个集合中的某个元素作为该集合的代表元素，
其它该集合中的元素都指向这个元素
当查找元素所在集合时，只要找到这个元素的指向的元素的最顶级元素即根，这个根就是代表节点
最后判断这两个元素的根是否相同即可
这里遇到一个问题，就是这个根元素怎么标记呢，可以让它所指向的元素是自己，这样询问时只要遇到指向元素是自己的元素，那么说明找到根了，即可停止
我们把这个指向的元素叫做这个元素的父亲
注意树不只有两层，因为在合并操作时集合被合并，原先两个集合的根中有一个变成了子节点，此时层数会增加，而这个代表元素是整棵树的根，这个点的父亲只是它的原来的集合的根，因为集合已经合并，所以判断两个元素是否在同一集合中时要用整棵树的根，因此要递归寻找这个元素的父亲直到元素的父亲是自身时停止寻找并返回该元素。当然这个过程可以循环解决，只需要定义临时变量为该元素的父亲，然后这个变量不断等于这个变量的父亲，直到其父亲等于自身为止，然后返回该变量即可
举例：
假设集合1以3为根，集合2以6为根，则
2和4的根分别是3和6，不等，所以不在一个集合
1和3的根分别是3和3，相等，所以在一个集合。
合并操作：
把两个元素 所在集合 合并为一个集合，合并后两个集合等同于在一个大集合中，此时一个元素所在集合的根要变成子节点，另一个作为大集合的根。
如何合并：
很简单，先查找两个元素的根，然后把一个根的父亲改为另一个根，这样就完成了合并 ，但是如果两个元素的根相同说明在一个集合就直接返回不用合并
例：
以查找时为例
合并前：
假设新根是6
合并后：
再查找2和4：
2的父亲是3，3的父亲是6，6的父亲是6
4的父亲是6
在一个集合
注意合并时要把一个根直接接到另一个根上，而不是接到子节点上！！
路径压缩
在查找时我们不关心这个元素的父亲，只要这个元素通过找父亲能找到根即可，所以每次查找后把查找的这条链上的元素的父亲直接改为根，这样不影响查找，而且减少以后查找的次数（减小树高）
递归时只要返回时return fa[x]=find(fa[x])即可，这样会递归到最后找到根把父亲从上往下回溯着改
循环法要找到根后再开一个循环，先让循环变量=它的父亲，然后把它的父亲改为根，直到 父亲=父亲 时停止（到根了），这是自下往上的。
但是一次只能保证这条链上的，不能是全树都改好，所以后面删除元素时比较麻烦
按秩合并：(启发式合并）
在合并时我们要将其中一个元素所在集合的根变为子节点，另一个变为新根，可是哪一个变为子节点呢？
显然将尺寸小的接到尺寸大的集合上更好，这样查找大的时还是那个复杂度，可反之要花更多的时间，但是尺寸小的集合造成影响小，所以要把尺寸小的接到尺寸大的集合上
但是尺寸是什么呢？
尺寸既可以是一个集合的元素个数即点数，也可以是树的高度，它们优化的效果是等价的
如果以点数为尺寸，那么合并时把点数小的根父亲等于点数大的根，点数大的根的点数+=点数小的根的点数，这个叫做启发式合并，其他数据结构也常用
如果以高度为尺寸，那么合并时把高度小的根父亲等于高度大的根，但是高度不变，为什么？ 这个叫做按秩合并，不是很常用
只要a的高度小于b，因为高度是整数，所以a的高度比b至少少一，把a接到b的下面，此时这个高度不能超过b
什么时候高度改变？当a和b高度相等时，可以随便接，但是无论怎么接高度都增加1
假如a接在b下面，那么b的这个子树的高度为b，而b的其他子树中最大的高度是b-1，因此b的高度变为b+1!
复杂度：
\(n\)个元素，\(m\)次操作（查找或合并）
空间复杂度：
由于每个元素都有一个父亲，所以\(fa\)数组大小是\(n\)，故空间复杂度\(O（n）\)
时间复杂度：
既使用路径压缩，又使用按秩合并:
每个操作平均时间复杂度\(O(α(n))\)
\(α\)是反阿克曼函数，近似于常数
总操作平均复杂度\(O(mα(n))\)
只使用路径压缩：
总操作平均复杂度\(O(mα(n))\)
总操作最坏复杂度\(O(m logn )\)
只使用按秩合并：
总操作平均复杂度\(O(m logn )\)
删除操作：
修改后的并查集支持单个元素的删除
但是需要注意的是删除不是说删除这个点和这个点所连的点，而是仅仅删除这个点，其余与他相连的点仍然在原并查集中，但这个点独立成一个集合
在完美形态的并查集中，每个节点的父亲都是根，此时删除一个节点就是把这个节点的父亲改为自己，这样不影响其他节点，但是实际上路径压缩只能将这条链上的节点的父亲改为根，所以实际并查集形态不可估计
删除2后
那么我们可以用盒子来代替这个真正的节点去合并，而我们真正的每一个节点都指向每一个盒子
详细：
每一个节点都对应一个盒子，每个节点的父亲起初都是对应的一个新盒子
当我们合并集合时，我们只合并节点指向的盒子的所在集合，仍然符合按秩合并
当我们删除时把节点的父亲改为一个新的，从未使用过的盒子，原盒子保持空，这样原来集合的关系可以通过这个空盒子保留
当我们查找时查找节点所在盒子的根
仍然可以用路径压缩
一旦这个节点被删除，就到了新盒子，此时这个节点和原来的集合并不在一个集合中，所以删除有效
删除的节点再和别的节点合并改变的是它新盒子的集合
与原来集合无关
还可以有还原操作，就是删除后把这个节点还原到它最近被删除的集合中，显然可以再合并 ，但也可以数组记录每个节点上一次被删除的盒子编号，然后把这个节点的指向改为上一次被删除的盒子编号，这样就完全还原上一次这个节点的形态，不需要合并了
[code]#include#include#includeusing namespace std;int fa[10006],fa1[90006],t=10007,lasts[10006]; inline int finds(int x ){ if(fa1[x]==x)return x; return fa1[x]=finds(fa1[x]);}inline void inserts(int x,int y){ int a=finds(x),b=finds(y); if(a==b)return; fa1[a]=b;}inline void deletes(int x){ lasts[x]=fa[x]; fa[x]=t; ++t;}inline void restore(int x){ fa[x]=lasts[x];}int main(){ memset(fa,-1,sizeof fa); memset(lasts,0,sizeof lasts); for(int i=0;i>m; for(int i=0;i>op; if(op=='U'){ cin>>x>>y; if(fa[x]==-1)fa[x]=x; if(fa[y]==-1)fa[y]=y; inserts(fa[x],fa[y]); }else if(op=='F'){ cin>>x>>y; if(fa[x]==-1)fa[x]=x; if(fa[y]==-1)fa[y]=y; if(finds(fa[x])!=finds(fa[y])){ coutn>>m; int cnt=0; for(int i=0;i>x>>y>>z; y=y+1;//闭区间改成开区间 if(fa[x]==-1)fa[x]=x; if(fa[y]==-1)fa[y]=y; int a=find(x),b=find(y); if(a!=b){ inserts(x,y,a,b,z); }else{ if(v[x]-v[y]!=z)cnt++; } } coutx>>y;// cout |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
