Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
dsu_potentialized.hpp
[詳解]
1#include "../../kyopro_library/template.hpp"
2
3/// @brief ポテンシャル付き DSU
4/// @tparam Group 群
5template<typename Group>
7 using Type=typename Group::Type;
8 DsuPotentialized()=default;
9
10 /// @brief コンストラクタ
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 各頂点を連結成分に分解する
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
67private:
68 vector<int> par,sz;
69 vector<Type> diff_weight;
70 int forest_count;
71};
ポテンシャル付き DSU
int size(int x)
頂点 x を含む連結成分のサイズを返す
DsuPotentialized()=default
Type weight(int x)
頂点 x のポテンシャルを返す
int count()
連結成分の個数を返す
vector< vector< int > > groups()
各頂点を連結成分に分解する
int find(int x)
頂点 x を含む連結成分の代表元を返す
DsuPotentialized(int n)
コンストラクタ
bool same(int x, int y)
頂点 x と y が同じ連結成分に属するか否かを返す
Type diff(int x, int y)
op(inv(weight(y)), weight(x)) (x と y の間のポテンシャル差)を返す
bool merge(int x, int y, Type w)
頂点 x と y を連結し、weight(x) = op(weight(y), w) とする