ufset.cpp 1.31 KB
Newer Older
CDK6182CHR's avatar
CDK6182CHR committed
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <utility>


/// <summary>
/// 具有固定长度的UFSet 数组实现
/// 暂时不考虑保存数据的问题 下标就是数据
/// </summary>
class UFSet {
	int* data;
	int size;
public:
	UFSet(int size_);
	~UFSet();
	UFSet(const UFSet&) = delete;
	UFSet(UFSet&& s)noexcept;
	UFSet& operator=(const UFSet&) = delete;
	UFSet& operator=(UFSet&& s)noexcept;

	int find(int x)const;
	int find(int x);    //带路径折叠
	int merge(int x, int y);
};

UFSet::UFSet(int size_):size(size_)
{
	data = new int[size];
	std::fill(data, data + size, -1);
}

UFSet::~UFSet()
{
	if (data)
		delete[] data;
	data = nullptr;
}

UFSet::UFSet(UFSet&& s) noexcept:
	data(s.data),size(s.size)
{
	s.size = 0;
	s.data = nullptr;
}

UFSet& UFSet::operator=(UFSet&& s) noexcept
{
	size = s.size;
	data = s.data;
	s.size = 0;
	s.data = nullptr;
	return *this;
}

int UFSet::find(int x) const
{
	while (data[x] >= 0)
		x = data[x];
	return x;
}

//把路径上所有的都折叠上去
int UFSet::find(int x)
{
	int root = static_cast<const UFSet*>(this)->find(x);
CDK6182CHR's avatar
CDK6182CHR committed
65
	while (x != root) {
CDK6182CHR's avatar
CDK6182CHR committed
66
		data[x] = root;
CDK6182CHR's avatar
CDK6182CHR committed
67
		x = data[x];
CDK6182CHR's avatar
CDK6182CHR committed
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
	}
	return root;
}

//不负责折叠路径
//只把y合并到x
//返回新的根节点
int UFSet::merge(int x, int y)
{
	int rx = find(x);
	int ry = find(y);
	data[rx] += data[ry];
	data[ry] = rx;
	return rx;
}