blob: b33a839938481027cc4bbcbc32694997e2d583aa (
plain) (
blame)
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
|
#ifndef DisjointSet_H__
#define DisjointSet_H__
#include <vector>
#include <cstdlib>
namespace meow{
class DisjointSet{
private:
size_t n;
std::vector<size_t> father;
std::vector<size_t> depth;
//
size_t _root(size_t now);
size_t _merge(size_t a, size_t b);
public:
DisjointSet();
DisjointSet(size_t _n);
DisjointSet(DisjointSet const& dsj);
//
size_t root (size_t a ) const;
size_t size ( ) const;
//
void reset(size_t _n );
size_t merge(size_t a, size_t b);
};
/*********************************************************
@asciidoc
=== meow:: *DisjointSet* (C++ class)
.Description
`DisjointSet` is a lighting data structure that maintain N numbers from
*0* to *N-1* with methods below:
[options="header",width="100%",cols="1>,1<s,5<,1<,1<,10<",grid="rows"]
|=======================================================================
|Const?|Name| Parameters| Return Type| Time Complexity| Description
|const|root|(size_t number)|size_t|very fast|
Return the *group id* of the number given
|const|size|()|size_t|very fast|
Return *N*
||reset|(size_t N)|void|very fast|
Clean and initalize
||merge|(size_t number1, +
size_t number2)|size_t|very fast|
*Union* the group contains number1 and the group contains number2.
Return the merged group id
|=======================================================================
NOTE: *very fast* means that you can consider it as constant time.
'''
@asciidoc-
*********************************************************/
}
#include "DisjointSet.hpp"
#endif // DisjointSet_H__
|
