【模板】可持久化并查集

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mid ((l+r)>>1)
const int INF=1e9+7,MAXNODE=24e6+7,MAXN=1e6+7;
int N,M,tmp[MAXN],rt[MAXN];
int fa[MAXNODE],dep[MAXNODE],lson[MAXNODE],rson[MAXNODE],sz;
void init(int &x,int l,int r){
    x=++sz;
    if(l==r){
        fa[x]=l;
        return;
    }
    init(lson[x],l,mid);
    init(rson[x],mid+1,r);
}
void modify(int &x,int l,int r,int p/*pre*/,int q/*pos*/,int v){
    x=++sz;
    if(l==r){
        fa[x]=v;
        dep[x]=dep[p];
        return;
    }
    lson[x]=lson[p];
    rson[x]=rson[p];
    if(q<=mid)
        modify(lson[x],l,mid,lson[p],q,v);
    else
        modify(rson[x],mid+1,r,rson[p],q,v);
}
int query(int x,int l,int r,int q){
    if(l==r)
        return x;
    if(q<=mid)
        return query(lson[x],l,mid,q);
    return query(rson[x],mid+1,r,q);
}
int findset(int edit,int loc){
    int f=query(edit,1,N,loc);
    if(fa[f]==loc)
        return f;
    return findset(edit,fa[f]);
}
void add_dep(int x,int l,int r,int loc){
    if(l==r){
        dep[x]++;
        return;
    }
    if(loc<=mid)
        add_dep(lson[x],l,mid,loc);
    else
        add_dep(rson[x],mid+1,r,loc);
}
int main(){
    scanf("%d%d",&N,&M);
    init(rt[0],1,N);
    for(int i=1;i<=M;i++){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            rt[i]=rt[i-1];
            int a,b;
            scanf("%d%d",&a,&b);
            int f1=findset(rt[i],a),f2=findset(rt[i],b);
            if(dep[f1]>dep[f2])
                swap(f1,f2);
            modify(rt[i],1,N,rt[i-1],fa[f1],fa[f2]);
            if(dep[f1]==dep[f2])
                add_dep(rt[i],1,N,fa[f2]);
        }else if (opt==2){
            int edit;
            scanf("%d",&edit);
            rt[i]=rt[edit];
        }else{
            rt[i]=rt[i-1];
            int a,b;
            scanf("%d%d",&a,&b);
            int f1=findset(rt[i],a),f2=findset(rt[i],b);
            puts(f1==f2?"1":"0");
        }
    }
    return 0;
}
代码

n个集合 m个操作

操作：

  • 1 a b 合并a,b所在集合

  • 2 k 回到第k次操作之后的状态(查询算作操作)

  • 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

1≤n≤105,1≤m≤2×105

 可持久化并查集实现

  1. 数据结构：可持久化数组∈主席树
  2. 思想：无路径压缩的并查集，可持久化数组维护fa数组，按照并查集方法合并
  3. 实现：
    1. 定义数组：（主席树常规数组） 
      int N,M,tmp[MAXN],rt[MAXN]每个版本线段树的根;
int fa[MAXNODE]维护数组（并查集数组）,dep[MAXNODE]联通块的最大深度,lson[MAXNODE]左儿子,rson[MAXNODE]右儿子,sz节点栈顶;
    2.  初始化：建树，每个叶子节点的值为当前点所对应的下标； 
      scanf("%d%d",&N,&M);
init(rt[0],1,N);
      void init(int &x,int l,int r){
    x=++sz;
    if(l==r){
        fa[x]=l;类似于并查集，每个点最初指向自己
        return;
    }
    init(lson[x],l,mid);
    init(rson[x],mid+1,r);
}
    3. 合并联通块： 
      scanf("%d%d",&a,&b);
int f1=findset(rt[i],a),f2=findset(rt[i],b);找到两个点的最高父亲在线段树中的下标
if(dep[f1]>dep[f2])启发式合并，让最大深度小的点连到大的上，防止树退化
    swap(f1,f2);
modify(rt[i],1,N,rt[i-1],fa[f1]f1的集合名,fa[f2]将f1的集合名改为f2的集合名);
if(dep[f1]==dep[f2])如果二者深度相等，合并后最大深度必然增加1，故将f2的深度加1
    add_dep(rt[i],1,N,fa[f2]);
      void modify(int &x,int l,int r,int p/*pre*/,int q/*pos*/,int v){
    x=++sz;
    if(l==r){
        fa[x]=v;
        dep[x]=dep[p];
        return;
    }
    lson[x]=lson[p];
    rson[x]=rson[p];
    if(q<=mid)
        modify(lson[x],l,mid,lson[p],q,v);
    else
        modify(rson[x],mid+1,r,rson[p],q,v);
}
int query(int x,int l,int r,int q){注意返回的是下标，不是集合名
    if(l==r)
        return x;
    if(q<=mid)
        return query(lson[x],l,mid,q);
    return query(rson[x],mid+1,r,q);
}
void add_dep(int x,int l,int r,int loc){
    if(l==r){
        dep[x]++;
        return;
    }
    if(loc<=mid)
        add_dep(lson[x],l,mid,loc);
    else
        add_dep(rson[x],mid+1,r,loc);
}
int findset(int edit,int loc){类似于并查集的操作
    int f=query(edit,1,N,loc);查找当前节点线段树中下标
    if(fa[f]==loc)
        return f;
    return findset(edit,fa[f]);
}
    4. 查询两点是否在同一集合：和并查集一样，比较两点findset值 
      int a,b;
scanf("%d%d",&a,&b);
int f1=findset(rt[i],a),f2=findset(rt[i],b);
puts(f1==f2?"1":"0");

 完整代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 #define mid ((l+r)>>1)
 5 const int INF=1e9+7,MAXNODE=24e6+7,MAXN=1e6+7;
 6 int N,M,tmp[MAXN],rt[MAXN];
 7 int fa[MAXNODE],dep[MAXNODE],lson[MAXNODE],rson[MAXNODE],sz;
 8 void init(int &x,int l,int r){
 9     x=++sz;
10     if(l==r){
11         fa[x]=l;
12         return;
13     }
14     init(lson[x],l,mid);
15     init(rson[x],mid+1,r);
16 }
17 void modify(int &x,int l,int r,int p/*pre*/,int q/*pos*/,int v){
18     x=++sz;
19     if(l==r){
20         fa[x]=v;
21         dep[x]=dep[p];
22         return;
23     }
24     lson[x]=lson[p];
25     rson[x]=rson[p];
26     if(q<=mid)
27         modify(lson[x],l,mid,lson[p],q,v);
28     else
29         modify(rson[x],mid+1,r,rson[p],q,v);
30 }
31 int query(int x,int l,int r,int q){
32     if(l==r)
33         return x;
34     if(q<=mid)
35         return query(lson[x],l,mid,q);
36     return query(rson[x],mid+1,r,q);
37 }
38 int findset(int edit,int loc){
39     int f=query(edit,1,N,loc);
40     if(fa[f]==loc)
41         return f;
42     return findset(edit,fa[f]);
43 }
44 void add_dep(int x,int l,int r,int loc){
45     if(l==r){
46         dep[x]++;
47         return;
48     }
49     if(loc<=mid)
50         add_dep(lson[x],l,mid,loc);
51     else
52         add_dep(rson[x],mid+1,r,loc);
53 }
54 int main(){
55     scanf("%d%d",&N,&M);
56     init(rt[0],1,N);
57     for(int i=1;i<=M;i++){
58         int opt;
59         scanf("%d",&opt);
60         if(opt==1){
61             rt[i]=rt[i-1];
62             int a,b;
63             scanf("%d%d",&a,&b);
64             int f1=findset(rt[i],a),f2=findset(rt[i],b);
65             if(dep[f1]>dep[f2])
66                 swap(f1,f2);
67             modify(rt[i],1,N,rt[i-1],fa[f1],fa[f2]);
68             if(dep[f1]==dep[f2])
69                 add_dep(rt[i],1,N,fa[f2]);
70         }else if (opt==2){
71             int edit;
72             scanf("%d",&edit);
73             rt[i]=rt[edit];
74         }else{
75             rt[i]=rt[i-1];
76             int a,b;
77             scanf("%d%d",&a,&b);
78             int f1=findset(rt[i],a),f2=findset(rt[i],b);
79             puts(f1==f2?"1":"0");
80         }
81     }
82     return 0;
83 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/guoshaoyang/p/10925066.html