并查集
1. 含义
并查集是一种管理元素所属集合的数据结构, 可以看作一个森林, 一棵树表示一个集合. 常用于判定图的连通性.
并查集支持两种操作:
- 合并(Unite): 合并两个元素所属的集合;
- 查询(Find): 查询某个元素所在树的根结点.
路径压缩: 查询过程中经过的每个元素都属于该集合, 故可将其看作直接连到根结点的树.
2. 实现
#pragma once
/**
* @file union_find.h
* @brief 并查集
* @author gendloop
*/
// c++
#include <vector>
class UnionFind {
private:
std::vector<int> parents_; ///< 每个元素的父结点
std::vector<int> ranks_; ///< 元素所在集合的秩
public:
UnionFind(int n);
/// 查找根结点
int find(int x);
/// 合并两个元素所在的集合
void unite(int x, int y);
// 判断两个元素是否在同一集合中
bool connected(int x, int y);
};
/**
* @file union_find.cpp
* @brief 并查集
* @author gendloop
*/
// local
#include "union_find.h"
UnionFind::UnionFind(int n)
{
parents_.resize(n);
ranks_.resize(n, 0); // 初始秩为零
for (auto i = 0; i < n; ++i) {
parents_[i] = i; // 元素初始父结点为自己, 表示根结点
}
}
int UnionFind::find(int x)
{
if (parents_[x] != x) {
parents_[x] = find(parents_[x]); // 路径压缩
}
return parents_[x];
}
void UnionFind::unite(int x, int y)
{
// 求两集合的根结点
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
// 将秩小的集合合并到秩大的集合下
if (ranks_[rootx] > ranks_[rooty]) {
parents_[rooty] = rootx;
}
else if (ranks_[rootx] < ranks_[rooty]) {
parents_[rootx] = rooty;
}
else {
parents_[rooty] = rootx;
ranks_[rootx]++;
}
}
}
bool UnionFind::connected(int x, int y)
{
return find(x) == find(y);
}
3. 拓展
- 带删除并查集
- 带权并查集