Reincarnation

正因为梦易碎，才格外美好。

并查集优化

发表于 更新于 分类于 ，
本文字数： 10k 阅读时长 ≈ 9 分钟

追根溯源的时候，或许会突然想起，自己在哪一条路上落下了什么，
回过身去，记忆的碎片随风而去，留下过往的泪水，怅然若失。

前言

想起自己曾多次遇到过这种事情，某一天的晚上乱刷题的时候，开了道非强制在线的动态图连通性，发现正解带撤销并查集， 挂飞了，然后就打算复习一下 讲的线段树分治，一开洛谷的模板题发现不会 维护二分图，就去逛题解区，结果又是带撤销并查集。

被迫无奈，滚回来写这篇博客。

并查集的优化

我们已经知道的是，并查集的复杂度是 ，并不是很好分析的样子，很容易被卡，一般而言：暴力维护是这样子的：

1
2
3
4
5
int getRt(int x)
{
    if(Rt[x]==x) return x;
    return getRt(Rt[x]);
}

很容易发现，这样的并查集稍不注意就是 ，所以衍生出两种优化：路径压缩和按秩合并。

路径压缩一般这样写：

1
2
3
4
int getRt(int x)
{
    return Rt[x]==x?x:Rt[x]=getRt(Rt[x]);
}

需要注意的是，路径压缩并不支持可持久化。

按秩合并一般这样写：

1
2
3
4
5
6
7
8
9
10
11
12
int Siz[MAXN];
inline void merge(int x,int y)
{
    x=getRt(x),y=getRt(y);
    if(x==y) return ;
    if(Siz[x]>Siz[y]) Rt[y]=x;
    else
    {
        if(Siz[x]==Siz[y]) ++Siz[y];
        Rt[x]=y;
    }
}

然后你会发现，路径压缩优化查询，按秩合并优化修改，两个一起用的话，被卡的几率近乎为零。（按秩合并的复杂度分析可以参考启发式）

两个优化加持的并查集复杂度为 。

可撤销并查集

这个好像用得更多一些。

注意：这里的可撤销指的是撤销上一次的操作，而非是在整个 内删除一条曾经存在的边。

基础实现

因为只需要撤销一次操作即可，那么我们考虑记录上一次的操作并尽量优化上一次操作的复杂度（因为考虑到撤销操作的复杂度应该和上一次是等价的），并且考虑让每一次操作修改的结点数尽量的少，那么就绝对不能进行路径压缩（路径压缩的复原会更改整棵子树），可以使用按秩合并。

那么我们考虑记录一个 函数表示每一个连通块的结点个数，每次进行启发式合并，查找的时候直接暴力查询即可。根据启发式合并的计算，每一个 都至多会被修改 次，然后一些卡常小技巧在于，递归调用函数的时间大于递推循环的时间，所以，不使用路径压缩的 find() 可以这样写：

1
2
3
4
5
inline int getRt(int x)
{
    while(x!=Rt[x]) x=Rt[x];
    return x;
}

然后合并这样写：

1
2
3
4
5
6
7
inline void merge(int u,int v)
{
    int p=getRt(u),q=getRt(v);
    if(p==q) return ;
    if(Siz[p]<Siz[q]) std::swap(p,q);
    Siz[p]+=Siz[q],Rt[q]=p;
}

撤销操作

注意到，每一次 merge() 会改变两个值： ，那我们记录两个 std::vector 来维护每一次的修改，学了一个高级的引用写法：

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
using Piir=std::pair<int&,int>;
struct Dsu
{
    int Rt[MAXN],Siz[MAXN];
    std::vector<Piir>His_Siz;
    std::vector<Piir>His_Rt;
    inline void init(int n)
    {
        for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1;
    }
    inline int getRt(int x)
    {
        while(x!=Rt[x]) x=Rt[x];
        return x;
    }
    inline void merge(int u,int v)
    {
        int p=getRt(u),q=getRt(v);
        if(p==q) return ;
        if(Siz[p]<Siz[q]) std::swap(p,q);
        His_Siz.push_back({Siz[p],Siz[q]});
        Siz[p]+=Siz[q];
        His_Rt.push_back({Rt[p],Rt[q]});
        Rt[q]=p;
    }
	inline int histroy(){ return His_Rt.size(); }
    inline void roll(int x)
    {
        while(His_Rt.size()>x)
        {
            His_Rt.back().first=His_Rt.back().second;
            His_Rt.pop_back();
            His_Siz.back().first=His_Siz.back().second;
            His_Siz.pop_back();
        }
    }
}Dsu;

封装形式（好复制）。

最终实现

我觉得这个看起来更好理解一些：（极限压行了解一下）

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
struct Dsu
{
	int Rt[MAXN],Siz[MAXN],Stk[MAXN],Top;
	inline void init(int n){ for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1; }
	inline int getRt(int x)
	{
		while(x!=Rt[x]) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p;
		Stk[++Top]=q;
	}
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x){ while(Top>x) back(); }
	inline bool connect(int x,int y){ return (getRt(x)==getRt(y)); }
}Dsu;

可持久化并查集

可持久化

熟练掌握 之后，就会发现并查集实际上并无法支持撤销（断边）操作，这是显然的，第一源于路径压缩会破坏原有的树型结构而导致其无法复原，二是并查集的父子关系与原图并不等价，导致断边操作出现错误。

但这并不代表并查集真的无法撤销（说了跟说了一样）。

我们不考虑断边，而是考虑撤销之前的操作，即回到历史版本，也就是熟知的可持久化。意思就是，现在我们需要扩展 使其支持三个操作：

  • 合并两个集合，即 merge() 操作，这是显然的；
  • 查找某个结点的祖先，即 getRt() 操作，同样显然；
  • 回到某次操作之前的状态，即可持久化。

我们要保证第三个操作的时间复杂度不能高于 ，这也是显然的，因为有主席树（可持久化线段树）的经验，或许理解这个东西就要轻松一点。

注意到并不能进行路径压缩，所以每一次查找的复杂度都会高达 ，然后会发现洛谷过不了，只有 。（甚至吸氧）

AC Code 
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// Problem: P3402 可持久化并查集
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3402
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
	read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(char c)
{
	putchar(c);
}
template<>
inline void write(char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
	write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
	x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
	x=x<y?x:y;
}
const int MAXN=1e7+10;
int N,Q;
struct Dsu
{
	int lc,rc,dep,fa;
}Dsu[MAXN];
int Rt[MAXN];
struct PDsu
{
	int Idx=0;
	#define ls(p) Dsu[p].lc
	#define rs(p) Dsu[p].rc
	void build(int &p,int l,int r)
	{
		p=++Idx;
		if(l==r) return Dsu[p].fa=l,void();
		int mid=(l+r)>>1;
		build(ls(p),l,mid),build(rs(p),mid+1,r);
	}
	void merge(int last,int &p,int l,int r,int x,int fa)
	{
		p=++Idx;Dsu[p]=Dsu[last];
		if(l==r)
		{
			Dsu[p].fa=fa,Dsu[p].dep=Dsu[last].dep;
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid) merge(Dsu[last].lc,Dsu[p].lc,l,mid,x,fa);
		else merge(Dsu[last].rc,Dsu[p].rc,mid+1,r,x,fa);
	}
	void upDate(int p,int l,int r,int x)
	{
		if(l==r) return ++Dsu[p].dep,void();
		int mid=(l+r)>>1;
		if(x<=mid) upDate(Dsu[p].lc,l,mid,x);
		else upDate(Dsu[p].rc,mid+1,r,x);
	}
	int query(int p,int l,int r,int x)
	{
		if(l==r) return p;
		int mid=(l+r)>>1;
		if(x<=mid) return query(Dsu[p].lc,l,mid,x);
		else return query(Dsu[p].rc,mid+1,r,x);
	}
	int getRt(int p,int x)
	{
		int now=query(p,1,N,x);
		if(Dsu[now].fa==x) return now;
		return getRt(p,Dsu[now].fa);
	}
	#undef ls
	#undef rs
}Pdsu;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);
	Pdsu.build(Rt[0],1,N);
	for(int i=1,opt,ql,qr;i<=Q;++i)
	{
		read(opt);
		if(opt==1)
		{
			read(ql,qr);
			Rt[i]=Rt[i-1];
			int vl=Pdsu.getRt(Rt[i],ql),vr=Pdsu.getRt(Rt[i],qr);
			if(Dsu[vl].fa!=Dsu[vr].fa)
			{
				if(Dsu[vl].dep>Dsu[vr].dep) std::swap(vl,vr);
				Pdsu.merge(Rt[i-1],Rt[i],1,N,Dsu[vl].fa,Dsu[vr].fa);
				if(Dsu[vl].dep==Dsu[vr].dep) Pdsu.upDate(Rt[i],1,N,Dsu[vr].fa);
			}
		}
		else if(opt==2) read(ql),Rt[i]=Rt[ql];
		else
		{
			read(ql,qr);
			Rt[i]=Rt[i-1];
			int vl=Pdsu.getRt(Rt[i],ql),vr=Pdsu.getRt(Rt[i],qr);
			if(Dsu[vl].fa==Dsu[vr].fa) puts("1");
			else puts("0");
		}
	}
	return 0;
}
/*

*/

当然，没有人说过可持久化 只有 的做法。可以考虑有 的做法。

好叭，我鸽了，因为学了时间戳 树之后谁还用可持久化啊。

另话

有一种 的离线做法，大概做法是：跑一棵 树，其结点在于操作的时间戳，然后进行 遍历，每次记录时间戳，然后再次到达这棵结点的时候撤销即可，这样的话并不需要可持久化，就直接用可撤销并查集就可以做到，跑的飞起（甚至最优解）。

AC Code 
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Problem: P3402 可持久化并查集
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3402
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
	read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c)
{
	putchar(c);
}
template<>
inline void write(char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
	while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
	write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
	x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
	x=x<y?x:y;
}
const int MAXN=3e5+10,MAXM=1e6+10;
const int INF=0x3f3f3f3f;
int N,Q;
bool ans[MAXN];
struct Dsu
{
	int Rt[MAXN],Siz[MAXN],Stk[MAXN],Top;
	inline void init(int n){ for(int i=1;i<=n;++i) Rt[i]=i,Siz[i]=1; }
	inline int getRt(int x)
	{
		while(x!=Rt[x]) x=Rt[x];
		return x;
	}
	inline void merge(int u,int v)
	{
		int p=getRt(u),q=getRt(v);
		if(p==q) return ;
		if(Siz[p]<Siz[q]) std::swap(p,q);
		Siz[p]+=Siz[q],Rt[q]=p;
		Stk[++Top]=q;
	}
	inline void back()
	{
		int q=Stk[Top--];
		Siz[Rt[q]]-=Siz[q],Rt[q]=q;
	}
	inline void back(int x){ while(Top>x) back(); }
	inline bool connect(int x,int y){ return (getRt(x)==getRt(y)); }
}Dsu;
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Tim[MAXN],Opt[MAXN],Qx[MAXN],Qy[MAXN];
void dfs(int x)
{
	Tim[x]=Dsu.Top;
	if(Opt[x]==3) ans[x]=Dsu.connect(Qx[x],Qy[x]);
	else if(Opt[x]==1) Dsu.merge(Qx[x],Qy[x]);
	for(int e=Head[x];e;e=Edge[e].next) dfs(Edge[e].to);
	Dsu.back(Tim[x]);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q);
	Dsu.init(N);
	for(int i=1;i<=Q;++i)
	{
		read(Opt[i],Qx[i]);
		if(Opt[i]!=2) read(Qy[i]),addEdge(i-1,i);
		else addEdge(Qx[i],i);
	}
	dfs(0);
	for(int i=1;i<=Q;++i) if(Opt[i]==3) write(ans[i],'\n');
	return 0;
}
/*

*/

终之章

或许 爷说的对，我学 可不是为了学些偏难怪的东西，不是看着什么高级就去搞（或许根本就不会考），脚踏实地吧。

草，又看见一个高级玩意儿叫可追溯化数据结构，考完 还是可以去搞一搞的。

相关文章