Union Find
(data-structure/unionfind/union_find.hpp)

• View this file on GitHub
• Last update: 2024-01-07 20:49:49+09:00
• Include: #include "data-structure/unionfind/union_find.hpp"

Description

Union find (disjoint set union, 素集合データ構造) は，素集合を管理するデータ構造である．

空間計算量: $O(n)$

Operations

• UnionFind(int n)
  • サイズnの union find を構築する．
  • 時間計算量: $O(n)$
• int find(int x)
  • $x$ が属する木の根を返す
  • 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
• void unite(int x, int y)
  • $x$ が属する集合と $y$ が属する集合を連結する
  • 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
• bool same(int x, int y)
  • $x$ と $y$ が同じ集合に属するかを判定する
  • 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$
• int size(int x)
  • $x$ が属する集合の大きさを返す
  • 時間計算量: $\mathrm{amortized}\ O(\alpha(n))$

Note

$\alpha(x)$ は逆アッカーマン関数である．

この実装では高速化に path compression と union by size を用いている．どちらか一方だと計算量は $O(\log n)$ になるが，両方使用することで $O(\alpha(n))$ になる．path compression の代わりに path splitting や path halving，union by size の代わりに union by rank といった実装手法もあり，どれも同じ計算量を実現する．

Reference

• Disjoint-set data structure
• UnionFindTree に関する知見の諸々
• Union Find の計算量の話
• データ構造をマージする一般的なテク
• Disjoint Set Union

Required by

• Static Range Union Find (data-structure/unionfind/static_range_union_find.hpp)
• Junction Tree (Width 2) (graph/junction_tree.hpp)
• Manhattan Minimum Spanning Tree (graph/manhattan_mst.hpp)
• Minimum Spanning Arborescence (graph/minimum_spanning_arborescence.hpp)
• Minimum Spanning Tree Algorithms (graph/mst.hpp)

Verified with

• test/aoj/GRL_2_A.boruvka.test.cpp
• test/aoj/GRL_2_A.kruskal.test.cpp
• test/aoj/GRL_2_A.prim.test.cpp
• test/yosupo/directedmst.test.cpp
• test/yosupo/manhattanmst.test.cpp
• test/yosupo/tree_decomposition_width_2.test.cpp
• test/yosupo/unionfind.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>

class UnionFind {
   public:
    UnionFind() = default;
    explicit UnionFind(int n) : data(n, -1) {}

    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
};

#line 2 "data-structure/unionfind/union_find.hpp"
#include <algorithm>
#include <vector>

class UnionFind {
   public:
    UnionFind() = default;
    explicit UnionFind(int n) : data(n, -1) {}

    int find(int x) {
        if (data[x] < 0) return x;
        return data[x] = find(data[x]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (data[x] > data[y]) std::swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return -data[find(x)]; }

   private:
    std::vector<int> data;
};

Back to top page