Weigthted Union Find
コードについての説明
重みつきの Union Find.
たとえば天秤を用いて 「おもり 1 がおもり 2 よりも $5$ g重く, おもり 2 がおもり 3 よりも $3$ g軽い」 みたいなことがわかっていれば 「おもり 1 はおもり 3 よりも $2$ g重い」ということがわかる.
このような推移的な関係(ここでは同じ連結成分内の 2 頂点間の重さの差)をうまく保持するデータ構造が Weigthted Union Find であり, Union Find の find 操作の際に, 親を根に付け替えるだけでなく同時に根との重みの差を伝播させることで Union Find と同じ計算量で行うことができる.
Union Find はこのようにある種の演算も効率良く行うことができる. この記事が参考になるかもしれない.
(関数)
unite$(a, b, w)$ : おもり $b$ がおもり $a$ よりも $w$ グラム重い
diff$(x, y)$ : おもり $y$ がおもり $x$ より何グラム重いかを返す
時間計算量: クエリ $\O (\alpha (m, n))$ ($\alpha (m, n)$ はアッカーマン関数の逆関数(参考))
コード
template<typename T> class Weighted_UnionFind
{
public:
int V;
vector<int> par,nrank;
vector<T> wd;
Weighted_UnionFind(int node_size) : V(node_size), par(V), nrank(V, 0), wd(V, 0){
iota(par.begin(), par.end(), 0);
}
int find(int x){
if(par[x] == x){
return x;
}else{
int parent = find(par[x]);
wd[x] += wd[par[x]];
return par[x] = parent;
}
}
T weight(int x){
find(x);
return wd[x];
}
void unite(int x,int y,T w){
w += weight(x), w -= weight(y);
x = par[x], y = par[y];
if(x == y) return;
if(nrank[x] < nrank[y]){
swap(x,y);
w = -w;
}
nrank[x] += (nrank[x] == nrank[y]);
par[y] = x;
wd[y] = w;
}
bool same(int x,int y){
return find(x) == find(y);
}
T diff(int x,int y){
return weight(y) - weight(x);
}
};
verify 用の問題
Atcoder : People on a Line 提出コード