目录
并查集是一种巧妙优雅的数据结构，主要用于解决元素分组和不相交集合的合并和查询问题。并查集是大量的树（单个节点也算是树）经过合并生成一系列家族森林的过程。
并查集的存储结构
并查集采用数组表示整个森林，初始时每个森林的树根为自己。
#define maxn 200
int fa[maxn+1];
void init(){
for(int i=0;i<=maxn;i++){
fa[i]=i;
}
}并查集查询
一般采用递归法实现对代表元素的查询：递归访问父节点，直至根节点（根节点的标志就是父节点)。根节点相同的两个元素属于同一个集合。所以判断A，B是否属于同一个集合直接判断find(A)和find(B)是否相同即可。
int find(int x){
if(fa[x]==x){
return x;
}
else{
return find(fa[x]);
}
}路径压缩
路径压缩是为了解决当树的高度过高的时候，提高查询时效的方法。
int find(int x){
if(x==fa[x]){
return x;
}
else{
fa[x]=find(fa[x]);
return fa[x];
}
}并查集合并
并查集合并就是将一棵树的根节点设置为另一棵树的根节点即可。
void merge(int i,int j){
fa[find(i)]=find(j);
}合并优化--启发式优化
合并时选择哪一棵树的根节点作为新树的根节点会影响未来操作时间复杂度。我们可以按照子树大小去合并，小的合并到大的，以免发生退化。所以启发式合并的原理是在集合合并时将小的结合合并到大的集合里，也可以使find操作的复杂度降低到，在集合合并时还要增加亿个更新集合大小的操作。
void merge(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
if(sz[x]<sz[y]){
swap(x,y);
}
sz[x]+=sz[y];
fa[y]=x;
}
}合并优化--按秩合并
其实这个合并和启发式合并是有些相似的，合并时同样会因为选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。但这次我们选择是树的秩。秩的意思就是树的高度，按秩合并就是每次合并两个的时候判断两边的树高，小的合并到大的上面去，这样就可以将深度较小的树连到另一棵，以免发生退化，也可以使find操作复杂度降低到，在集合合并时还要增加一个更新树高的操作。
注意：路径压缩和按合并一起使用会影响rank的准确性，所以普遍使用普通的合并与优化后的查找即可。
void merge(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
if(rk[x]>rk[y]){
swap(x,y);
}
if(rk[x]==rk[y]){
rk[y]++;
}
f[x]=y;
}
}可撤销并查集
可撤销并查集是一种扩展了标准并查集的数据结构，它允许在进行连接和查询操作的同时，能够回退或者撤销之前的操作。这种数据结构通常用于支持一些需要回滚操作的应用，比如在离线算法中，或者需要进行回退的决策问题中，当然主要是应用于在线算法，因为离线算法反悔可以完全输入后在一起处理。
例题
解析
针对这个题目，可以使用并查集来表示联通，很容易就能完成前两个操作1和操作2.
但是第三个操作，我们先在不考虑路径压缩和启发式合并的情况下，并查集的合并为：
Fa[find(i)]=j，我们只需要用变量记录t=find(i)和m=Fa(find(i))，当反悔的时候我们直接Fa[t]=m即可
但是既没有考虑路径压缩，有没有做启发式，查询效率是非常低的，很难通过一些复杂的题目。
无法使用压缩路径来优化并查集，因为使用压缩路径撤销时无法回到上一步。
所以可以在合并方式上面使用启发式合并或者按秩合并。
算法原理
1.查找
由于支持撤销操作，那么肯定不能压缩路径，否则会破坏树形结构，反悔时无法找到原本的父节点
2.合并
既然不能路径压缩，那么查询的复杂度就是O(d)(d为树的深度)的，所以要尽可能减少树的深度，于是用到了一种合并方法--启发式合并（或按秩合并）
3.撤销
用栈来记录每次合并的操作，然后进行对fa,size等变量的维护即可。
重要操作实现
#include<bits/stdc++.h>
int n,q;
int fa[20000005],siz[20000005];
//fa用于表示每个城市所属的集合的父节点，siz用于表示每个集合的大小
struct UndoObject{
int pos,val;//表示城市的位置和值
UndoObject(int p,int v){
pos=p;
val=v;
}
};
stack<UndoObject>undo_sz,undo_fa;
void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
while(!undo_sz.empty()){
undo_sz.pop();//清空之前栈的内容
}
while(!undo_fa.empty()){
undo_fa.pop();
}
}
int find(int x){
if(x==fa[x]){
return x;
}
return find(fa[x]);
}
void merge(int u,int v){
int x=find(u);
int y=find(v);
if(x==y){
return;
}
if(siz[x]<siz[y]){
swap(x,y);
}
undo_sz.push(UndoObject(x,siz[x]));
siz[x]+=siz[y];
undo_fa.push(UndoObject(y,fa[y]));
fa[y]=x;
}
void undo(){//撤销
fa[undo_fa.top().pos]=undo_fa.top().val;
undo_fa.pop();
siz[undo_sz.top().pos]=undo_sz.top().val;
undo_sz.pop();
}
