CF-ITMO公开课-并查集-STEP1

原文链接：Disjoint Sets Union - Codeforces

并查集，第一部分

并查集(DSU)是一种数据结构，能够在 $n$ 个元素上维护不相交的集合，并且支持下面两种操作：

• get(a)- 返回元素a所属集合的标识符。
• union(a, b)- 合并包含a和b的两个集合。

例如，我们可以调用get(a)和get(b)以比较a和b是否属于同一集合。

定义集合标识符的最简单方法是什么？ — 我们可以选择集合的领导者。

让我们维护一个数组p，其中p[a]是元素a所属集合的标识符（领导者）。

下面是两个函数的伪代码：

init():  
	p = new int[n]  
	for i in 1..n:    
		p[i] = i
get(a):  
	return p[a]
union(a, b):  
	a = p[a]  
	b = p[b]  
	for i in 1..n:    
		if p[i] == a:      
			p[i] = b

函数get(a)只是返回集合的领导者，而函数union(a, b)获取两个集合的领导者，并把所有a集合的元素的领导者设置为b集合的领导者。

不幸的是，这个算法太慢了：get的复杂度是$O(1)$，但是union的复杂度是$O(n)$。有没有办法改进这个算法呢？

让我们考虑最简单的想法 — 我们不是遍历所有元素，而是遍历a所在集合的元素。为此，对于每个集合，我们将维护一个链表l[a]。当我们需要合并两个集合时，我们只需将两个链表链接在一起。

init():  
	p = new int[n]  
	l = new List[n]  
	for i in 1..n:    
		p[i] = i    
	l[i] = { i }
get(a):  
	return p[a]
union(a, b):  
	a = p[a]  
	b = p[b]  
	for x in l[a]:    
		p[x] = b  
	l[b].append(l[a])

现在，get(a)的时间复杂度为$O(1)$，而union(a, b)的时间复杂度为$O(|l[a]|)$。不幸的是，这种复杂度还不够好：有可能找到一种执行方式，使得union的平均时间复杂度为$O(n)$。

考虑以下执行顺序：

• union(1, 2)，其中$|l[1]|=1$，$|l[2]|=1$，
• union(2, 3)，其中$|l[2]|=2$，$|l[3]|=1$，
• union(3, 4)，其中$|l[3]|=3$，$|l[4]|=1$，

依此类推。

所有操作的总时间为$1+2+3+…+(n−1)=O(n^2)$，因此union仍然是$O(n)$。如何改进呢？注意，主要问题在于我们总是将第一个集合连接到第二个集合。但如果我们将最小的集合连接到最大的集合会怎样呢？那么，union的代码将变成以下形式。

union(a, b):  
	a = p[a]  
	b = p[b]  
	if size(l[a]) > size(l[b]):    
		swap(a, b)  
	for x in l[a]:    
		p[x] = b  
	l[b].append(l[a])

我们比较两个集合，如果集合a的大小大于集合b，我们就交换它们。

注意，我们可以在$O(1)$的时间内实现size(l[a]) — 为此，我们必须将链表的大小单独存储。

这个算法的运行速度如何？

get(a)仍然在$O(1)$的时间内运行，但我们改进了union(a, b)吗？让我们计算一下我们改变x的领导者的次数，即算法执行p[x] = b的次数。

第一次改变x的领导者是当我们将它与更大的集合合并时。这意味着联合的大小至少为$2$。第二次改变x的领导者是当我们将集合与大小至少为$2$的更大集合合并时。这意味着联合的大小至少为$4$。

依此类推。我们只有在与更大的集合合并时才改变x的领导者。

由于我们将所有集合一起合并，每个元素的改变次数为$O(logn)$，因此总时间复杂度为$O(nlogn)$。由于有$n−1$次联合操作，平均时间复杂度为$O(logn)$。