Union-Find
(lib/data_structure/union_find.hpp)

• View this file on GitHub
• Last update: 2024-11-18 03:54:10+09:00
• Include: #include "lib/data_structure/union_find.hpp"

Union Find

使い方

• UnionFind(N): 要素数 N の Union Find を構築します。
• root(x): 集合 x の根を取得します。
• unite(x, y): 集合 x と y を併合します。
• same(x, y): x と y の属する集合が等しいかどうかを判定します。
• size(x): x の属する集合の大きさを取得します。
• edge(x): x の属する集合に張られている辺の本数を取得します。

計算量

• UnionFind(N): $\mathrm{O}(N)$
• root(x): 償却 $\mathrm{O}(\alpha(N))$ (アッカーマンの逆関数)
• unite(x, y): 償却 $\mathrm{O}(\alpha(N))$
• same(x, y): 償却 $\mathrm{O}(\alpha(N))$
• size(x): 償却 $\mathrm{O}(\alpha(N))$
• edge(x): 償却 $\mathrm{O}(\alpha(N))$

Required by

• Range Parallel Union-Find (lib/data_structure/range_parallel_union_find.hpp)
• T-join Problem (lib/graph/T_join.hpp)
• Manhattan MST (lib/graph/manhattanMST.hpp)
• lib/graph/rooted_tree_topological_order_with_minimum_inversions.hpp

Verified with

• test/library_checker/data_structure/range_parallel_unionfind.test.cpp
• test/library_checker/data_structure/unionfind.test.cpp
• test/library_checker/geometry/manhattanmst.test.cpp
• test/library_checker/graph/cycle_detection_undirected.test.cpp
• test/library_checker/graph/minimum_spanning_tree.test.cpp
• test/library_checker/tree/rooted_tree_topological_order_with_minimum_inversions.test.cpp

Code

#pragma once

/**
 * @brief Union-Find
 * @docs docs/data_structure/union_find.md
 */

#include <vector>
#include <cassert>

struct UnionFind{
    int V;
    std::vector<int> par;
    std::vector<int> edg;

    UnionFind(const int N) : V(N), par(N), edg(N){
        for(int i = 0; i < N; ++i){
            par[i] = -1;
            edg[i] = 0;
        }
    }

    int root(int x){
        assert(0 <= x && x < V);
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    int unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            edg[rx]++;
            return rx;
        }
        if(-par[rx] < -par[ry]) std::swap(rx, ry);
        par[rx] = par[rx] + par[ry];
        par[ry] = rx;
        edg[rx] += edg[ry] + 1;
        return rx;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return -par[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};

#line 2 "lib/data_structure/union_find.hpp"

/**
 * @brief Union-Find
 * @docs docs/data_structure/union_find.md
 */

#include <vector>
#include <cassert>

struct UnionFind{
    int V;
    std::vector<int> par;
    std::vector<int> edg;

    UnionFind(const int N) : V(N), par(N), edg(N){
        for(int i = 0; i < N; ++i){
            par[i] = -1;
            edg[i] = 0;
        }
    }

    int root(int x){
        assert(0 <= x && x < V);
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    int unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry){
            edg[rx]++;
            return rx;
        }
        if(-par[rx] < -par[ry]) std::swap(rx, ry);
        par[rx] = par[rx] + par[ry];
        par[ry] = rx;
        edg[rx] += edg[ry] + 1;
        return rx;
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    long long size(int x){
        return -par[root(x)];
    }

    long long edge(int x){
        return edg[root(x)];
    }
};

Back to top page