并查集简介

并查集是一种树形结构,用于处理一些不交集的合并及查询问题

Find:确定元素属于哪一个子集。这个方法就是不断向上查找到它的根节点,它可以用来确定两个元素是否属于同一子集

Union:将两个子集合并成同一个集合

并查集的实现

初始化并查集

把每一个元素都初始化为一个集合。

初始化之后,每一个元素的父亲节点就是它本身,每一个元素的祖先节点也是它本身。

1
2
3
4
5
6
void make_set(vector<T> data) {
for (T var : data) {
father.insert({ var,var });
size.insert({ var,1 });
}
}

查找一个元素所在的集合

1
2
3
4
5
6
7
8
9
T find_set(T node) {//查找一个元素的根节点
T f = father[node];
if (node != f) {
node = f;
f = find_set(f);
}
father[node] = f;//将沿途所有元素的父节点都改为根节点 //路径压缩
return f;
}

判断两个元素是否为同一个集合

1
2
3
bool isSame_set(T a, T b) { //返回两个元素是否是同一个集合
return find_set(a) == find_set(b);
}

合并两个元素所在的两个集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void union_set(T a, T b) {//合并两个集合
T aHead = find_set(a);
T bHead = find_set(b);
if (aHead != bHead) {
int aSize = size[aHead];
int bSize = size[bHead];
if (aSize > bSize) { //按秩合并
father[b] = a;
size[a] += size[b];
}

else {
father[a] = b;
size[b] += size[a];
}
}
}