洛谷P3402【模板】可持久化并查集
思路：
思路和可持久化线段树很相似，都是将主席树与另一种数据结构结合。这个是以并查集结合，所以维护数组fa和用于按秩合并的dep。
首先要建一棵树，这棵树的叶子结点初始化成其对应的下标，即并查集中fa[i]=i的初始化操作
然后对于查询操作，直接求对应历史版本的两个点是否fa相同即可
连边操作：先找到两个点所在并查集的头结点，若它们已经在一个块中，就跳过，否则比较dep大小，按秩合并：将小的连向大的（将时间复杂度降到n*logn）
若两个并查集的深度不同，则合并成一个后，深度为较大那个点的深度。若相同，需要把深度++（modify操作）
#include<bits/stdc++.h> using namespace std; #define mid ((l+r)>>1) #define N 3000005 int lc[N],rc[N],ndnum=0,dep[N],fa[N],n,ed[N]; void build(int s,int l,int r) { //非叶子节点的fa[]为空 if(l==r) { fa[s]=l; return ; }//一开始每一个节点的父亲是自己 build(lc[s]=++ndnum,l,mid); build(rc[s]=++ndnum,mid+1,r); } int query(int s,int l,int r,int pos) { if(l==r) return s; if(pos<=mid) return query(lc[s],l,mid,pos); else return query(rc[s],mid+1,r,pos); } void modify(int s,int l,int r,int pos) { if(l==r){ dep[s]++; return ; } if(pos<=mid) modify(lc[s],l,mid,pos); else modify(rc[s],mid+1,r,pos); } void copynode(int a,int b)//在原来的基础上新增一条链 { lc[a]=lc[b]; rc[a]=rc[b]; } void merge(int last,int &rt,int l,int r,int pos,int Fa) { rt=++ndnum;lc[rt]=lc[last],rc[rt]=rc[last]; if(l==r) { fa[rt]=Fa; dep[rt]=dep[last]; return ; } if(pos<=mid)merge(lc[last],lc[rt],l,mid,pos,Fa); else merge(rc[last],rc[rt],mid+1,r,pos,Fa); } int get_fa(int s,int pos)//找到的是对应点在主席树中的编号 fa[get_fa()]即为对应点的父亲 { int now=query(s,1,n,pos);//s==version?? if(fa[now]==pos) return now; return get_fa(s,fa[now]); } int main() { int m,a,b,op; scanf("%d%d",&n,&m); build(ed[0]=++ndnum,1,n); for(int i=1;i<=m;i++){ scanf("%d",&op); if(op==1){ ed[i]=ed[i-1];//这里要复制前面的版本 scanf("%d%d",&a,&b); int f1=get_fa(ed[i],a); int f2=get_fa(ed[i],b);//f1 f2是对应的编号 if(fa[f1]==fa[f2]) continue; if(dep[f1]>dep[f2]) swap(f1,f2); merge(ed[i-1],ed[i],1,n,fa[f1],fa[f2]);//ed[i]是未知的 由最终merge后的节点编号决定 所以要打& //若深度不同 那么深度是较深的一个 所以不需要改变 if(dep[f1]==dep[f2]) modify(ed[i],1,n,fa[f2]);//如果深度一样就需要将其中一个深度++ } if(op==2) scanf("%d",&a),ed[i]=ed[a]; if(op==3){ scanf("%d%d",&a,&b); ed[i]=ed[i-1];//每一次记得把前一次的版本复制过来 int f1=get_fa(ed[i],a),f2=get_fa(ed[i],b); if(fa[f1]==fa[f2]) printf("1 "); else printf("0 "); } } } /* 5 6 1 1 2 3 1 2 2 0 3 1 2 2 1 3 1 2 */