并查集

1. 简介

并查集是一种高效的数据结构，常用来解决集合的合并和查找问题，常见于图论问题中。

2. 操作

2.1 构建

并查集一般构建为初始时每个节点所属的集合编号即为自己的节点编号。

1
2
3
4
5
6
7
// 初始化
int father[MAXN];   // father[i] 即为节点 i 所属的集合编号
void init(int n) {
    for(int i = n; i; --i) {
        father[i] = i;
    }
}

2.2 查找

并查集的高效之处在于在查找过程中压缩路径，从而实现压缩路径后查找的效率变为 O(1) 。

1
2
3
4
// 寻找并查集的根节点
int findfather(int x) {
    return x == father[x] ? x : (father[x] = findfather(father[x]));
}

2.3 合并

每次合并时只需将一个集合的根节点的 father 设为另一个集合的根节点。

1
2
3
4
// 合并并查集
void mergefather(int x, int y) {
    father[father[x]] = father[y];
}

【注】不是 father[x] = y ，father[x] 改变的只是 x 的根节点，而不是整个并查集的根节点，因为并查集本质是依靠其根节点来维护的，所以应该将并查集的根节点的 father 修改为已另一个集合的根节点，从而保证前一个集合被合并到了后一个集合中。

3. 模板

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
#include <bits/stdc++.h>
using namespace std;

#ifndef _DSF_
#define _DSF_
#define ll long long 
#define MAXN 505

// 并查集
struct dsf {
    ll father[MAXN];   // father[i] 即为节点 i 所属的集合编号
    dsf() {}
    //初始化
    void init(ll n) {
        for(ll i = n; i; --i) {
            father[i] = i;
        }
    }
    // 寻找并查集的根节点
    ll findfather(ll x) {
        return x == father[x] ? x : (father[x] = findfather(father[x]));
    }
    // 合并并查集(将 x 节点所在并查集合并到 y 节点所在并查集)
    void mergefather(ll x, ll y) {
        father[father[x]] = father[y];
    }
};
#endif