并查集

April 15, 2018

算法

使用并查集可以快速判断两个元素是否属于同一个集合。

算法 #

基本思路 #

使用树来表示集合。

初始时，所有元素都分别是一棵树。
若两个元素属于同一个集合，则用一个元素作为另一个元素的孩子。

实现

数据结构：

fa[i] : 保存元素i的祖先

第一步：初始化

for(int i=0; i < n; ++i)
    fa[i] = i;	// 初始时，所有元素都分别是一棵树(祖先是自己）

第二步：根据关系构造并查集

// 查找树根
int find(int x) 
{
    if(fa[x] == x) return x;
    return find(fa[x]);
}

int temp_a, temp_b;
for(int i=0; i < m; ++i){
	cin >> a >> b;  // a, b属于同一集合
    temp_a = find(a), temp_b = find(b);
    fa[a] = b;
}

Note: 先找到树根，不管相不相同，都让a是b的孩子。

第三步：查询方法

for(int i=0; i < T; ++i){
	cin >> a >> b;
	if(find(a) == find(b)) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Note: 判断树根是否相同即可。

优化 #

降低树的深度（路径压缩）

find 操作耗费时间取决于树的深度，因此，如果在 find 执行过程让树的深度降低，则可以降低后续操作所需的时间。

方法： 让树根的后代们尽量都是树根的孩子。

// 查找树根
int find(int x) 
{
    if(fa[x] == x) return x;
    //return find(fa[x]);
    return fa[x] = find(fa[x]);
}

Note: fa[x] = find(fa[x]) 的值为左值 fa[x] ，等价于先fa[x] = find(fa[x]); 再 return fa[x]; 。

让小树接在大树上

每次发生树的拼接之后的 find 操作都需要重新降低树的深度，而显然元素少的树接到元素多的树上，需要的重组次数较少。

例子：

灰色圆圈即为要重组的元素，显然小接大要合算。

实现方法：

r[i] : 表示以元素i为根的树的相对大小

// 封装一下
void Union(int a, int b)
{
    int temp_a = find(a), temp_b = find(b);
    if(r[temp_a] >= r[temp_b]) {
    	fa[b] = a;  //小树的父亲等于大树
        if(r[temp_a] == r[temp_b])
        	++r[a]; // b为a的孩子->树变大了
    }
	else fa[a] = b;
}

for(int i=0; i < n; ++i) {
        fa[i] = i;	
        r[i] = 0;	// 记得初始化
}
for(int i=0; i < m; ++i) {
	cin >> a >> b;  // a, b属于同一集合
	Union(a,b);
}

实验 #

输入：

输出：

Yes
Yes
Yes
Yes
No

完整代码：

// 并查集
#include <iostream>
using namespace std;

const int MAXN = 100;
int fa[MAXN], r[MAXN], n, m; // n为元素数,m为关系数

// 查找树根
int find(int x)
{
    if(fa[x] == x) return x;
    return find(fa[x]);
}

void Union(int a, int b)
{
    int temp_a = find(a), temp_b = find(b);
        if(r[temp_a] >= r[temp_b]){
            fa[b] = a;  //小树的父亲等于大树
            if(r[temp_a] == r[temp_b])
                ++r[a]; // b为a的孩子->树变大了
        }
        else fa[a] = b;
}

int main()
{
    cin >> n;   
    // 初始化
    for(int i=0; i < n; ++i) {
        fa[i] = i;	// 初始时，所有元素都分别是一棵树(祖先是自己）
        r[i] = 0;
    }
    cin >> m;
    // 构造并查集
    int a, b;
    for(int i=0; i < m; ++i) {
        cin >> a >> b;  // a, b属于同一集合
        Union(a,b);
    }
    // 查询
    int T;
    cin >> T;
    for(int i=0; i < T; ++i) {
        cin >> a >> b;
        if(find(a) == find(b)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

复杂度分析 #

优化前的算法

算法复杂度主要取决于：1. 构造并查集 2. 查询操作

构造并查集复杂度分析：

查询find操作递归次数不会超过树的深度，树的深度不会大于n，因此，find操作复杂度为O(logn)。

构造时时间花费主要在find操作上，且要执行2m次find操作。因此构造并查集的时间复杂度为O(2mlogn), 忽略常数为O(mlogn)。

查询操作复杂度分析：

查询操作需要两次find操作，时间复杂度为O(logn)。

优化后的算法

先说结论：O((n+m)log*n) ，其中log*为增长及其缓慢的迭代函数，通常可以视为常数。

证明为构造性证明，较为复杂，这里不做扩展。