DSU (Disjoint Set Union)
(ds/dsu/dsu.hpp)

View this file on GitHub
Last update: 2026-07-13 06:09:24+09:00
Include: #include "ds/dsu/dsu.hpp"

Overview

A Disjoint Set Union (also known as Union-Find) data structure. It manages a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near constant time operations to merge sets and find the representative of a set.

It is implemented using Path Compression and Union by Size, achieving an amortized time complexity of $O(\alpha(N))$ per operation, where $\alpha$ is the inverse Ackermann function.

Complexity Notation

N is the number of elements.

Interface

struct Dsu {
    Dsu();
    explicit Dsu(int n);

    int merge(int a, int b);

    template <class Callback>
    int merge(int a, int b, Callback&& callback);

    bool same(int a, int b);
    int leader(int a);
    int size(int a);
    std::vector<std::vector<int>> groups();
};

Methods

Method	Description	Complexity
`Dsu()`	Creates an empty DSU.	$O(1)$
`explicit Dsu(int n)`	Creates `n` singleton sets.	$O(N)$
`int merge(int a, int b)`	Merges the sets containing `a` and `b`; returns the leader of the merged set.	Amortized $O(\alpha(N))$
`int merge(int a, int b, Callback&& callback)`	Merges two sets, invokes the callback after an actual merge, and returns the new leader.	Amortized $O(\alpha(N))$ plus callback work
`bool same(int a, int b)`	Returns whether `a` and `b` are in the same set.	Amortized $O(\alpha(N))$
`int leader(int a)`	Returns the representative of the set containing `a`.	Amortized $O(\alpha(N))$
`int size(int a)`	Returns the size of the set containing `a`.	Amortized $O(\alpha(N))$
`std::vector<std::vector<int>> groups()`	Returns all sets as vectors of element indices.	$O(N \alpha(N))$

Merge Callback

The callback overload invokes

callback(new_leader, absorbed_leader);

after two previously distinct components have been merged. At callback time, new_leader is already the combined component’s leader and leader(absorbed_leader) == new_leader. If the vertices were already connected, the callback is not invoked.

This is useful for external component aggregates. Store each aggregate at its leader, merge the two entries in the callback, and query through the current leader:

std::vector<long long> sum = initial_values;

auto combine = [&](int new_leader, int absorbed_leader) {
    sum[new_leader] += sum[absorbed_leader];
};

dsu.merge(a, b, combine);
long long component_sum = sum[dsu.leader(vertex)];

The entry at absorbed_leader becomes stale and does not need to be cleared, because that vertex cannot become a leader again.

Example

#include "ds/dsu/dsu.hpp"
#include <iostream>
#include <vector>

int main() {
    m1une::ds::Dsu dsu(5);
    std::vector<int> sum = {1, 2, 3, 4, 5};

    auto combine = [&](int new_leader, int absorbed_leader) {
        sum[new_leader] += sum[absorbed_leader];
    };

    dsu.merge(0, 1, combine);
    dsu.merge(2, 3, combine);
    dsu.merge(1, 2, combine);

    std::cout << dsu.same(0, 3) << '\n';  // 1
    std::cout << dsu.size(0) << '\n';  // 4
    std::cout << sum[dsu.leader(3)] << '\n';  // 1 + 2 + 3 + 4 = 10
}

Required by

Verified with

Code

#ifndef M1UNE_DSU_HPP
#define M1UNE_DSU_HPP 1

#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

struct Dsu {
   private:
    int _n;
    // parent_or_size[i] is the parent of i if it's >= 0.
    // If it's < 0, then i is a root and -parent_or_size[i] is the size of the group.
    std::vector<int> parent_or_size;

    // Returns {new leader, absorbed leader}. The absorbed leader is -1 when
    // both vertices already belong to the same component.
    std::pair<int, int> merge_leaders(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return {x, -1};
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return {x, y};
    }

   public:
    Dsu() : _n(0) {}
    explicit Dsu(int n) : _n(n), parent_or_size(n, -1) {}

    // Merges the group containing 'a' with the group containing 'b'.
    // Returns the leader of the merged group.
    int merge(int a, int b) {
        return merge_leaders(a, b).first;
    }

    // Invokes callback(new_leader, absorbed_leader) after an actual merge.
    // Returns the leader of the merged group.
    template <class Callback>
    int merge(int a, int b, Callback&& callback) {
        std::pair<int, int> merged = merge_leaders(a, b);
        if (merged.second != -1) callback(merged.first, merged.second);
        return merged.first;
    }

    // Returns true if 'a' and 'b' belong to the same group.
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    // Returns the leader (representative) of the group containing 'a'.
    int leader(int a) {
        if (parent_or_size[a] < 0) return a;
        // Path compression
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    // Returns the size of the group containing 'a'.
    int size(int a) {
        return -parent_or_size[leader(a)];
    }

    // Returns a list of all groups, where each group is a vector of its elements.
    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DSU_HPP

#line 1 "ds/dsu/dsu.hpp"



#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

struct Dsu {
   private:
    int _n;
    // parent_or_size[i] is the parent of i if it's >= 0.
    // If it's < 0, then i is a root and -parent_or_size[i] is the size of the group.
    std::vector<int> parent_or_size;

    // Returns {new leader, absorbed leader}. The absorbed leader is -1 when
    // both vertices already belong to the same component.
    std::pair<int, int> merge_leaders(int a, int b) {
        int x = leader(a), y = leader(b);
        if (x == y) return {x, -1};
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return {x, y};
    }

   public:
    Dsu() : _n(0) {}
    explicit Dsu(int n) : _n(n), parent_or_size(n, -1) {}

    // Merges the group containing 'a' with the group containing 'b'.
    // Returns the leader of the merged group.
    int merge(int a, int b) {
        return merge_leaders(a, b).first;
    }

    // Invokes callback(new_leader, absorbed_leader) after an actual merge.
    // Returns the leader of the merged group.
    template <class Callback>
    int merge(int a, int b, Callback&& callback) {
        std::pair<int, int> merged = merge_leaders(a, b);
        if (merged.second != -1) callback(merged.first, merged.second);
        return merged.first;
    }

    // Returns true if 'a' and 'b' belong to the same group.
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    // Returns the leader (representative) of the group containing 'a'.
    int leader(int a) {
        if (parent_or_size[a] < 0) return a;
        // Path compression
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    // Returns the size of the group containing 'a'.
    int size(int a) {
        return -parent_or_size[leader(a)];
    }

    // Returns a list of all groups, where each group is a vector of its elements.
    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }),
                     result.end());
        return result;
    }
};

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

DSU (Disjoint Set Union)
(ds/dsu/dsu.hpp)

Overview

Complexity Notation

Interface

Methods

Merge Callback

Example

Required by

Verified with

Code

DSU (Disjoint Set Union) (ds/dsu/dsu.hpp)

Overview

Complexity Notation

Interface

Methods

Merge Callback

Example

Required by

Verified with

Code

DSU (Disjoint Set Union)
(ds/dsu/dsu.hpp)