Weighted Union-Find - 重み付き素集合データ構造
(Library/DataStructure/WeightedUnionFind.hpp)

• View this file on GitHub
• Last update: 2025-04-30 01:32:17+09:00
• Include: #include "Library/DataStructure/WeightedUnionFind.hpp"

Weighted Union-Find - 重み付き素集合データ構造

$N$ 頂点からなる無向グラフに対して、辺の重みを管理しながら連結成分を管理するデータ構造です。

各要素間の重み（ポテンシャル）をアーベル群 $A$ で管理します。

Function

Constructor

WeightedUnionFind(int n)

• 頂点数 $n$ で重み付き Union Find を初期化します。
• 初期状態では、すべての頂点は独立しており、各頂点の重みは $0$ です。

制約

• $1 \le n \le 10^6$

計算量

• $\textrm{O}(n)$

---

Find

int Find(const int k)

• 頂点 $k$ が属する連結成分の代表元を返します。
• 経路圧縮を行いながら、頂点 $k$ までの重みを更新します。

制約

• $0 \le k < n$

計算量

• $\textrm{O}(\alpha(n))$ （$\alpha$ はアッカーマン関数の逆関数）

---

Weight

Abel Weight(const int k)

• 頂点 $k$ の代表元からの重み（ポテンシャル）を返します。

制約

• $0 \le k < n$

計算量

• $\textrm{O}(\alpha(n))$

---

Diff

Abel Diff(const int x, const int y)

• 頂点 $x$ から頂点 $y$ への重みの差分 Weight(y) - Weight(x) を返します。

制約

• $0 \le x, y < n$

計算量

• $\textrm{O}(\alpha(n))$

---

Same

bool Same(const int x, const int y)

• 頂点 $x$ と頂点 $y$ が同じ連結成分に属するかを判定します。

制約

• $0 \le x, y < n$

計算量

• $\textrm{O}(\alpha(n))$

---

Unite

bool Unite(int x, int y, Abel w)

• 頂点 $x$ と頂点 $y$ を重み $w$ の辺で連結します。
• Weight(y) - Weight(x) = w となるように連結されます。
• 既に連結されている場合は false を返し、新たに連結された場合は true を返します。

制約

• $0 \le x, y < n$
• $w \in A$

計算量

• $\textrm{O}(\alpha(n))$

---

Depends on

• Library/Common.hpp

Verified with

• verify/AOJ-DSL-1-B.test.cpp
• verify/LC-UnionfindWithPotential.test.cpp

Code

#include "../Common.hpp"

template<typename Abel = int32_t>
class WeightedUnionFind{
    public:
    WeightedUnionFind(int n) : data_(n, -1), weight_(n, Abel{}){}

    int Find(const int k){
        if(data_[k] < 0) return k;
        int r = Find(data_[k]);
        weight_[k] += weight_[data_[k]];
        return data_[k] = r;
    }

    Abel Weight(const int k){
        Find(k);
        return weight_[k];
    }

    Abel Diff(const int x, const int y){
        return Weight(y) - Weight(x);
    }

    bool Same(const int x, const int y){
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y, Abel w){
        w += Weight(x) - Weight(y);
        x = Find(x), y = Find(y);
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y), w = -w;
        data_[x] += data_[y];
        data_[y] = x;
        weight_[y] = w;
        return true;
    }

    private:
    vector<int> data_;
    vector<Abel> weight_;
};

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/DataStructure/WeightedUnionFind.hpp"

template<typename Abel = int32_t>
class WeightedUnionFind{
    public:
    WeightedUnionFind(int n) : data_(n, -1), weight_(n, Abel{}){}

    int Find(const int k){
        if(data_[k] < 0) return k;
        int r = Find(data_[k]);
        weight_[k] += weight_[data_[k]];
        return data_[k] = r;
    }

    Abel Weight(const int k){
        Find(k);
        return weight_[k];
    }

    Abel Diff(const int x, const int y){
        return Weight(y) - Weight(x);
    }

    bool Same(const int x, const int y){
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y, Abel w){
        w += Weight(x) - Weight(y);
        x = Find(x), y = Find(y);
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y), w = -w;
        data_[x] += data_[y];
        data_[y] = x;
        weight_[y] = w;
        return true;
    }

    private:
    vector<int> data_;
    vector<Abel> weight_;
};

Back to top page