BZOJ3673/3674 可持久化并查集

对于并查集我们有两种优化

一、按秩合并

描述：就是在对两个不同子集连接时，按照rank来连，也就是rank低的连在rank高的下面。rank高的做父亲节点。

作用，这样类似维护了一棵树，树是rank高的在上。

二、路径压缩

描述：假如fa数组已经嵌套了N层，那么传统的做法去找祖先要做N次，当N很大时，这种做法很没效率。

这种思想可以应用到dp，搜索，数据结构等等方面。

对于按秩合并，我们既将小的连在大的上面这样每次都不会超过1/2，所以复杂度自然就是log级的，想一想不按秩合并的话为何可能会变成O(n)

对于路径压缩，我们既将get过一边父亲的点直接记下来，类似于记忆化搜索，也能很大的提高效率。但请读者注意，并非所有时刻我们都能将并查集写成f[x]=get(f[x])

因为对于类似于P1014最小生成数个数我们不能采用路径压缩因为我们关心几个点的连通性，压缩后就会破坏他们之间的连通关系，一旦删去中间一条边就可能不连通。

下面给出代码By：大奕哥

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e7+10;
 4 int rt[N],sz,n,m,deep[N],last;
 5 struct node{
 6     int l,r,v;
 7 }t[N];
 8 void build(int &k,int l,int r)
 9 {
10     if(!k)k=++sz;
11     if(l==r){t[k].v=l;return;}
12     int mid=l+r>>1;
13     build(t[k].l,l,mid);build(t[k].r,mid+1,r);
14 }
15 void modify(int l,int r,int x,int &y,int pos,int val)
16 {
17     y=++sz;t[y]=t[x];//类似主席树的思想直接连过来 
18     if(l==r){t[y].v=val;deep[y]=deep[x];return;}
19     int mid=l+r>>1;
20     if(pos<=mid)modify(l,mid,t[x].l,t[y].l,pos,val);
21     else modify(mid+1,r,t[x].r,t[y].r,pos,val);
22 }
23 void add(int x,int l,int r,int pos)
24 {
25     if(l==r){deep[x]++;return;}
26     int mid=l+r>>1;
27     if(pos<=mid)add(t[x].l,l,mid,pos);
28     else add(t[x].r,mid+1,r,pos);
29 }
30 int query(int x,int l,int r,int pos)
31 {
32     if(l==r)return x;
33     int mid=l+r>>1;
34     if(mid>=pos)return query(t[x].l,l,mid,pos);
35     else return query(t[x].r,mid+1,r,pos);
36 }
37 int find(int x,int k)
38 {
39     int p=query(x,1,n,k);
40     if(k==t[p].v)return p;
41     
42     return find(x,t[p].v);  //这个是直接做
43     
44     int y=find(x,t[p].v);
45     modify(1,n,x,x,t[p].v,y);
46     return y;  // 这个是路径压缩，找出来的时候顺便修改这样以后再次访问就会提高效率
47 }
48 int main()
49 {
50     scanf("%d%d",&n,&m);
51     build(rt[0],1,n);int f,x,y,k;
52     for(int i=1;i<=m;++i)
53     {
54         scanf("%d",&f);
55         if(f==1){
56             rt[i]=rt[i-1];
57             scanf("%d%d",&x,&y);
58             int fx=find(rt[i],x),fy=find(rt[i],y);
59             if(t[fx].v==t[fy].v)continue;
60             if(deep[fx]>deep[fy])swap(fx,fy);//按秩合并，小的往大的上并 
61             modify(1,n,rt[i-1],rt[i],t[fx].v,t[fy].v);
62             if(deep[fx]==deep[fy])add(rt[i],1,n,t[fy].v);//相等的话我们就将父节点秩加一 
63         }
64         else if(f==2){
65             scanf("%d",&k);rt[i]=rt[k];
66         }
67         else{
68             rt[i]=rt[i-1];
69             scanf("%d%d",&x,&y);
70             int fx=find(rt[i],x),fy=find(rt[i],y);
71             if(t[fx].v==t[fy].v)last=1;
72             else last=0;
73             printf("%d
",last);
74         }
75     }
76     return 0;
77 }

BZOJ3673/3674 可持久化并查集

相关推荐