120 lines
3.1 KiB
C++
120 lines
3.1 KiB
C++
#pragma once
|
|
|
|
#include <iostream>
|
|
#include <vector>
|
|
#include <map>
|
|
|
|
namespace Lenyiin
|
|
{
|
|
class UnionFindSet
|
|
{
|
|
public:
|
|
// 初始化: 为每个元素单独分配一个集合, 初始时每个集合大小为 1, 用 -1 表示
|
|
UnionFindSet(int n)
|
|
: _v(n, -1) // 初始化所有元素都为根节点, 且集合大小为1
|
|
{
|
|
}
|
|
|
|
// 查找操作: 找到元素 x 所属集合的根节点, 并使用路径压缩优化
|
|
int FindRoot(int x)
|
|
{
|
|
int root = x;
|
|
// 查找根节点, 沿着父节点链向上寻找
|
|
while (_v[root] >= 0)
|
|
{
|
|
root = _v[root];
|
|
}
|
|
|
|
// 路径压缩: 将路径上所有节点直接挂在根节点下
|
|
while (x != root)
|
|
{
|
|
int parent = _v[x]; // 保存当前节点的父节点
|
|
_v[x] = root; // 将当前节点直接连接到根节点
|
|
x = parent; // 继续处理父节点
|
|
}
|
|
|
|
return root; // 返回根节点
|
|
}
|
|
|
|
// 合并两个集合: 使用按秩合并优化
|
|
bool Union(int x1, int x2)
|
|
{
|
|
int root1 = FindRoot(x1);
|
|
int root2 = FindRoot(x2);
|
|
|
|
// 如果本身就在一个集合里, 则无需合并
|
|
if (root1 == root2)
|
|
{
|
|
return false;
|
|
}
|
|
|
|
// 按秩合并: 始终将较小的集合挂到较大的集合上
|
|
if (_v[root1] < _v[root2]) // root1 集合规模较大（负值越小, 集合越大）
|
|
{
|
|
_v[root1] += _v[root2]; // 增加 root1 集合的大小
|
|
_v[root2] = root1; // root2 挂到 root1 上
|
|
}
|
|
else
|
|
{
|
|
_v[root2] += _v[root1]; // 增加 root2 集合的大小
|
|
_v[root1] = root2; // root1 挂到 root2 上
|
|
}
|
|
|
|
return true; // 合并成功
|
|
}
|
|
|
|
// 判断两个元素是否在同一个集合中
|
|
bool InSet(int x1, int x2)
|
|
{
|
|
return FindRoot(x2) == FindRoot(x2);
|
|
}
|
|
|
|
// 统计当前集合的个数
|
|
size_t SetSize()
|
|
{
|
|
size_t count = 0;
|
|
for (auto e : _v)
|
|
{
|
|
if (e < 0) // 只有根节点存储负值, 表示集合的大小
|
|
{
|
|
++count;
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
// 打印当前并查集的结构 (用于调试)
|
|
void Print() const
|
|
{
|
|
for (int i = 0; i < _v.size(); ++i)
|
|
{
|
|
printf("v[%d] == %d\n", i, _v[i]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
private:
|
|
std::vector<int> _v; // 存储每个元素的父节点或集合大小
|
|
};
|
|
}
|
|
|
|
// namespace Lenyiin
|
|
//{
|
|
// template <class T>
|
|
// class UnionFindSet
|
|
// {
|
|
// public:
|
|
// UnionFindSet(const T* a, size_t n)
|
|
// {
|
|
// for (size_t i = 0; i < n; ++i)
|
|
// {
|
|
// _v.push_back(a[i]);
|
|
// _indexmap[a[i]] = i;
|
|
// }
|
|
// }
|
|
//
|
|
// private:
|
|
// vector<T> _v; // 人找编号
|
|
// map<T, int> _indexmap; // 编号找人
|
|
// };
|
|
// }
|