Disjoint Set Union (graph/dsu.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-18 22:02:23+07:00
• Include: #include "graph/dsu.hpp"

Description

Disjoint Set Union (DSU) with union by size and path compression. Supports efficient union and find operations in nearly constant time per operation.

Operations

• DSU(int n)
  • Constructs DSU with n elements
  • Time complexity: $\mathcal O(n)$
• void reset(int n)
  • Resets the DSU to have n elements (all in separate sets)
  • Time complexity: $\mathcal O(n)$
• int find(int x)
  • Returns the representative of the set containing x
  • Time complexity: $\mathcal O(\alpha(n))$ amortized
• bool same(int x, int y)
  • Returns whether x and y are in the same set
  • Time complexity: $\mathcal O(\alpha(n))$ amortized
• int size(int x)
  • Returns the size of the set containing x
  • Time complexity: $\mathcal O(\alpha(n))$ amortized
• bool merge(int x, int y)
  • Merges the sets containing x and y. Returns true if they were in different sets
  • Time complexity: $\mathcal O(\alpha(n))$ amortized
• bool merge(int x, int y, F &&f)
  • Merges the sets containing x and y and calls f(rep(x), rep(y)) where rep(x) is the new root
  • Returns true if they were in different sets
  • Time complexity: $\mathcal O(\alpha(n))$ amortized

Verified with

• test/yosupo/ds/unionfind.test.cpp
• test/yosupo/graph/minimum_spanning_tree_kruskal.test.cpp

Code

#pragma once

struct DSU {
    vector<int> data;
    DSU() : DSU(0) {}
    DSU(int n) : data(n, -1) {}

    void reset(int n) {
        if (data.size() < n) data.resize(n);
        fill_n(begin(data), n, -1);
    }
    int size(int x) { return -data[find(x)]; }
    int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        return merge(x, y, [](auto...) {});
    }
    template<class F> bool merge(int x, int y, F &&f) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += exchange(data[y], x);
        f(x, y);
        return true;
    }
};

#line 2 "graph/dsu.hpp"

struct DSU {
    vector<int> data;
    DSU() : DSU(0) {}
    DSU(int n) : data(n, -1) {}

    void reset(int n) {
        if (data.size() < n) data.resize(n);
        fill_n(begin(data), n, -1);
    }
    int size(int x) { return -data[find(x)]; }
    int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        return merge(x, y, [](auto...) {});
    }
    template<class F> bool merge(int x, int y, F &&f) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += exchange(data[y], x);
        f(x, y);
        return true;
    }
};

Back to top page