モノイド付きUnion Find (DataStructure/union_find_with_monoid.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-08-25 23:31:57+09:00
• Include: #include "DataStructure/union_find_with_monoid.hpp"

モノイド付きUnion Find (UnionFindWithMonoid)

atcoder::dsu を継承し、結合時に関数をフックできる Union-Find です。
成分併合の際に op(from, to) が一度呼び出されます。

コンストラクタ

UnionFindWithMonoid(int N)

N 頂点（0..N-1）で初期化します。

計算量

• $O(N)$

merge（拡張版）

int merge(int u, int v, std::function<void(int, int)> op)

頂点 u と v を属する成分同士で併合します。
すでに同成分のときは統合を行わず、代表元 leader(u) を返します（op は呼ばれません）。
異なる成分*ときのみ併合が実行され、内部で atcoder::dsu::merge(u, v) を呼び、新しい代表元を to、吸収される代表元を from として ちょうど一度 op(from, to) を呼びます。

• op(from, to) は「from の成分の情報を to の成分へ統合する」ための処理を書いてください。

戻り値

• 併合後の代表元 to（同成分だった場合は leader(u)）

制約

• 0 ≤ u, v < N

計算量

• ならし $O(\alpha(N))$（アッカーマン関数の逆関数）

その他の機能

本クラスは atcoder::dsu を継承しているため、以下の関数もそのまま使用できます。

• leader(int v)
• same(int u, int v)
• size(int v)
• groups()

関連情報

• AtCoder Library dsu: 依存クラス

Verified with

• test/DataStructure/union_find_with_monoid/aoj-2664.cpp

Code

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;

class UnionFindWithMonoid : public atcoder::dsu
{
public:
    UnionFindWithMonoid(int N) : atcoder::dsu(N) {}

    int merge(int u, int v, function<void(int, int)> op)
    {
        if (this->same(u, v))
        {
            return this->leader(u);
        }

        u = this->leader(u), v = this->leader(v);

        int to = atcoder::dsu::merge(u, v);
        int from = u ^ v ^ to;
        op(from, to);

        return to;
    }
};

#line 1 "DataStructure/union_find_with_monoid.hpp"
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;

class UnionFindWithMonoid : public atcoder::dsu
{
public:
    UnionFindWithMonoid(int N) : atcoder::dsu(N) {}

    int merge(int u, int v, function<void(int, int)> op)
    {
        if (this->same(u, v))
        {
            return this->leader(u);
        }

        u = this->leader(u), v = this->leader(v);

        int to = atcoder::dsu::merge(u, v);
        int from = u ^ v ^ to;
        op(from, to);

        return to;
    }
};

Back to top page