zzoce 🧊
并查集

并查集

Thu Oct 03 2024
zzcoe
9 分钟
数据结构与算法 数据结构 启发式
1215 字

并查集是一种树形结构，主要用于处理一些不相交的集合和合并以及查询的问题

一般并查集#

查询根节点#

如果 x 的根节点不是自己，则 x=parent[x]，继续查找

CPP
1
2
3
4
5
6
7
int find(int x){
    while(parent[x]!=x){
		x=parent[x];
	}
	return x;
}

合并#

将 J 合并到 I 的根节点上，J 的根节点等于 i 的根节点，此时 J 与 I 为兄弟

PLAINTEXT
1
2
3
void merge(int i,int j){
    Parent[find(j)] = find(i);
}

启发式并查集#

带路径压缩的更节点查询#

CPP
1
2
3
4
5
6
7
8
9
10
11
12
int find(int x){//路径压缩,使得并查集的树不至于太高而浪费时间
    int a=x;
	while (Parent[a]!=a){
		a=Parent[a];
	}
	while (Parent[x]!=a){
		int t=Parent[x];
		Parent[x]=a;
		x=t;
	}
	return a;
}

合并优化#

将较小的树合并大大树上，使得树的高度尽可能不增长，数组 sz 用来存储树的高度

CPP
1
2
3
4
5
6
7
8
9
10
11
12
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if (fx!=fy){
		if (sz[fx]<sz[fy]){
		//使得fx树更大
			swap(fx,fy);
		}
		sz[fx]+=sz[fy];
		Parent[y]=fx;
	}
}

可撤销并查集#

可撤销并查集是一种扩展了标准并查集数据结构的数据结构，它允许在进行连接和查询操作的同时，能够回退或者撤销之前的操作，这种数据结构通常用于支持一些需要回滚操作的应用，主要应用于在线算法。

可撤销的关键#

  1. 母树保存其合并前的大小，即 sz
  2. 子树保存其合并前的父节点 以上两点分别使用两个栈实现，撤销时母树还原其大小，子树还原其父节点

算法原理#

1.在可撤销并查集中不可以使用压缩路径，但是可以使用合并优化， 2. 采用启发式合并（或按秩合并）的方法来降低树的高度 3. 用栈来记录每次合并的操作，然后对 Parent，sz 等变量进行维护即可 4. 伪代码：在合并时 Parent[find (x)]=find(y)，只需要用变量记录 t=find(x),m=Parent[find (x)]（实际上 t 和 m 相等），在撤销时 Parent[t]=t 即可

撤销栈#

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
const int MAXN=1e5+5;
int n,q;
int Parent[MAXN*10],sz[MAXN*10];
struct UndoObject{
	int pos,val;
	UndoObject(int p,int v){
		this->pos=p;
		this->val=v;
	}
};
stack <UndoObject>undo_sz,undo_fa;
//undo_fa中val表示pos节点在合并前的根节点
//undo_sz中val表示pos节点在合并前的大小

初始化#

CPP
1
2
3
4
5
6
7
8
9
10
	for (int i=1;i<=n;i++){
		Parent[i];
		sz[i]=1;
	}
	while (!undo_sz.empty()){//清空栈
		undo_sz.pop();
	}
	while (!undo_fa.empty()){
		undo_fa.pop();
	}

查询根节点#

CPP
1
2
3
4
5
6
int find (x){
	while (Parent[x]!=x){
		x=Parent[x];
	}
	return x;
}

可撤销优化合并#

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void merge(int u,int v){
	int fu=find (u);
	int fv=find (v);
	if (fu==fv){
		return ;
	}else if (sz[fu]<sz[fv]){
	//fu所在的树更大
		swap(fu,fv);
	}
	//fv合并到fu上，fv较小
	undo_sz.push(UndoObject(fu,sz[fu]));//fu及其大小
	sz[fu]+=sz[fv];
	undo_fa.push(UndoObject(fv,Parent[fv]));//fv及其根节点
	Parent[fv]=fu;
	return ;
}

撤销#

CPP
1
2
3
4
5
6
void undo(){
	Parent[undo_fa.top().pos]=undo_fa.top().val;
	undo_fa.pop();
	sz[undo_sz.top().pos]=undo_sz.top().val;
	undo_sz.pop();
}

可持久化并查集#

P3402 可持久化并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

==一种可以支持回退，访问之前版本的并查集==。前置知识：[[算法笔记/数据结构/线段树#可持久化线段树（主席树）|主席树]]

并查集的核心就是 fa 数组，想要可持久化并查集，只需要维护不同版本的 fa 数组就可以了！！！！！！！

注意： 不可以使用路径压缩，但可以使用按秩合并。如果使用按秩合并那就还需要一个可持续化数组来维护每个节点的深度，也就是维护 dep 数组

综上，需要维护两个可持久化数组，分别是 fa 数组，dep 数组

![[Pasted image 20240505183450.png]]

CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
struct node {
    int l,r;
    int val;//dep
}tr[MAXN*40*2];
int n;
int tot,rootfa[MAXN],rootdep[MAXN];
void build (int &u,int l,int r){//建树
    u=++tot;
    if (l==r){
        tr[u].val=l;
        return ;
    }
    int m=(l+r)>>1;
    build (tr[u].l,l,m);
    build (tr[u].r,m+1,r);
}
void modify(int &u,int v,int l,int r,int pos,int val){//点修，修改fa/dep
    u=++tot;
    tr[u]=tr[v];
    if (l==r){
        tr[u].val=val;
        return ;
    }
    int m=(l+r)>>1;
    if (pos<=m){
        modify(tr[u].l,tr[v].l,l,m,pos,val);
    }else {
        modify(tr[u].r,tr[v].r,m+1,r,pos,val);
    }
}
int query (int u,int l,int r,int pos){
    if (l==r){
        return tr[u].val;
    }
    int m=(l+r)>>1;
    if (pos<=m){
        return query(tr[u].l,l,m,pos);
    }else {
        return query(tr[u].r,m+1,r,pos);
    }
}
int find (int u,int x){
    int fx= query(rootfa[u],1,n,x);
    return fx==x?x:find (u,fx);
}
void merge (int u,int x,int y){
    x=find (u-1,x);
    y=find (u-1,y);
    if (x==y){
        rootfa[u]=rootfa[u-1];
        rootdep[u]=rootdep[u-1];
    }else {
        int depx= query(rootdep[u-1],1,n,x);
        int depy= query(rootdep[u-1],1,n,y);
        if (depx<depy){
            modify(rootfa[u],rootfa[u-1],1,n,x,y);
            rootdep[u]=rootdep[u-1];
        }else if (depx>depy){
            modify(rootfa[u],rootfa[u-1],1,n,y,x);
            rootdep[u]=rootdep[u-1];
        }else {
            modify(rootfa[u],rootfa[u-1],1,n,y,x);
            Modify (rootdep[u], rootdep[u-1], 1, n, x, depx+1);

        }
    }

}
Int main ()
{
    Int m;
    Cin>>n>>m;
    Build (rootfa[0], 1, n);
    For (int ver=1; ver<=m; ver++){
        Int opt, x, y;
        Cin>>opt;
        Switch (opt){
            Case 1:
                Cin>>x>>y;
                Merge (ver, x, y);
                Break;
            Case 2:
                Cin>>x;
                Rootfa[ver]=rootfa[x];
                Rootdep[ver]=rootdep[x];
                Break;
            Case 3:
                Cin>>x>>y;
                Rootfa[ver]=rootfa[ver-1];
                Rootdep[ver]=rootdep[ver-1];
                Int fx=find (ver, x);
                Int fy=find (ver, y);
                cout<<(fx==fy?1:0)<<endl;
                Break;
        }
    }
    Return 0;
}