Kyopro Library
読み取り中…
検索中…
一致する文字列を見つけられません
dsu_potentialized.hpp
[詳解]
1
#
include
"../../kyopro_library/template.hpp"
2
3
/// @brief ポテンシャル付き DSU
4
/// @tparam Group 群
5
template
<
typename
Group>
6
struct
DsuPotentialized
{
7
using
Type=
typename
Group::Type;
8
DsuPotentialized
()=
default
;
9
10
/// @brief コンストラクタ
11
DsuPotentialized
(
int
n) {
12
par.resize(n); iota(par.begin(),par.end(),0);
13
sz=vector<
int
>(n,1);
14
diff_weight=vector<Type>(n,Group::id());
15
forest_count=n;
16
}
17
18
/// @brief 頂点 x を含む連結成分の代表元を返す
19
int
find
(
int
x) {
20
if
(par[x]==x)
return
x;
21
int
root=find(par[x]);
22
diff_weight[x]=Group::op(diff_weight[x],diff_weight[par[x]]);
23
return
par[x]=root;
24
}
25
26
/// @brief 頂点 x と y を連結し、weight(x) = op(weight(y), w) とする
27
bool
merge
(
int
x,
int
y, Type w) {
28
w=Group::op(Group::inv(
weight
(
y
)
),Group::op(w,
weight
(
x
)
));
29
x=
find
(
x
)
; y=
find
(
y
)
;
30
if
(x==y)
return
false
;
31
if
(sz[x]<sz[y]) {
32
swap(x,y);
33
w=Group::inv(w);
34
}
35
par[y]=x; sz[x]+=sz[y]; diff_weight[y]=w;
36
forest_count--;
37
return
true
;
38
}
39
40
/// @brief 頂点 x のポテンシャルを返す
41
Type
weight
(
int
x) {
42
find
(
x
)
;
43
return
diff_weight[x];
44
}
45
46
/// @brief op(inv(weight(y)), weight(x)) (x と y の間のポテンシャル差)を返す
47
Type
diff
(
int
x,
int
y) {
return
Group::op(diff_weight[y],Group::inv(diff_weight[x])); }
48
49
/// @brief 頂点 x を含む連結成分のサイズを返す
50
int
size
(
int
x) {
return
sz[find(x)]; }
51
52
/// @brief 頂点 x と y が同じ連結成分に属するか否かを返す
53
bool
same
(
int
x,
int
y) {
return
find
(
x
)
==
find
(
y
)
; }
54
55
/// @brief 連結成分の個数を返す
56
int
count
() {
return
forest_count; }
57
58
/// @brief 各頂点を連結成分に分解する
59
vector
<
vector
<
int
>>
groups
() {
60
int
n=par.size();
61
vector<vector<
int
>> ret(n);
62
for
(
int
i=0; i<n; i++) ret[find(i)].push_back(i);
63
ret.erase(remove_if(ret.begin(),ret.end(),[&](
const
vector<
int
>& v) {
return
v.empty(); }),ret.end());
64
return
ret;
65
}
66
67
private
:
68
vector<
int
> par,sz;
69
vector<Type> diff_weight;
70
int
forest_count;
71
};
DsuPotentialized
ポテンシャル付き DSU
Definition
dsu_potentialized.hpp:6
DsuPotentialized::size
int size(int x)
頂点 x を含む連結成分のサイズを返す
Definition
dsu_potentialized.hpp:50
DsuPotentialized::DsuPotentialized
DsuPotentialized()=default
DsuPotentialized::weight
Type weight(int x)
頂点 x のポテンシャルを返す
Definition
dsu_potentialized.hpp:41
DsuPotentialized::count
int count()
連結成分の個数を返す
Definition
dsu_potentialized.hpp:56
DsuPotentialized::groups
vector< vector< int > > groups()
各頂点を連結成分に分解する
Definition
dsu_potentialized.hpp:59
DsuPotentialized::find
int find(int x)
頂点 x を含む連結成分の代表元を返す
Definition
dsu_potentialized.hpp:19
DsuPotentialized::DsuPotentialized
DsuPotentialized(int n)
コンストラクタ
Definition
dsu_potentialized.hpp:11
DsuPotentialized::same
bool same(int x, int y)
頂点 x と y が同じ連結成分に属するか否かを返す
Definition
dsu_potentialized.hpp:53
DsuPotentialized::diff
Type diff(int x, int y)
op(inv(weight(y)), weight(x)) (x と y の間のポテンシャル差)を返す
Definition
dsu_potentialized.hpp:47
DsuPotentialized::merge
bool merge(int x, int y, Type w)
頂点 x と y を連結し、weight(x) = op(weight(y), w) とする
Definition
dsu_potentialized.hpp:27
graph
dsu_potentialized.hpp
構築:
1.13.2