Union-Find - 素集合データ構造
(Library/DataStructure/UnionFind.hpp)

• View this file on GitHub
• Last update: 2025-04-30 01:32:17+09:00
• Include: #include "Library/DataStructure/UnionFind.hpp"

Union-Find - 素集合データ構造

$n$ 頂点の無向グラフに対し、

• $2$ 頂点を結ぶ辺の追加
• $2$ 頂点が連結であるかの判定

をならし $\textrm{O}(\alpha(n))$ 時間で処理することができるデータ構造です。

Function

Constructor

UnionFind(size_t n)

• $n$ 頂点 $0$ 辺の無向グラフを構築します。
• 頂点には $0, 1, \dots, n - 1$ の番号が振られているとします。

制約

• $0 \le n \le 10^6$

計算量

• $\textrm{O}(n)$

---

Find

int Find(const int k)

• 頂点 $k$ が属する連結成分の代表頂点を取得します。
• 内部処理として経路圧縮を行います。

制約

• $0 \le k \lt n$

計算量

• ならし $\textrm{O}(\alpha(n))$

---

Same

bool Same(const int x, const int y)

• 頂点 $x$ と頂点 $y$ が連結であるかを判定します。
• 頂点 $x$ と頂点 $y$ が連結であるとき true を返します。

制約

• $0 \le x, y \lt n$

計算量

• ならし $\textrm{O}(\alpha(n))$

---

Unite

bool Unite(int x, int y)

• 頂点 $x$ と頂点 $y$ の間に辺 $(x, y)$ を追加します。
• 辺 $(x, y)$ の追加により頂点 $x$ と頂点 $y$ が連結になったとき true を返します。

制約

• $0 \le x, y \lt n$

計算量

• ならし $\textrm{O}(\alpha(n))$

---

Size

size_t Size(int k)

• 頂点 $k$ の属する連結成分の頂点数を返します。

制約

• $0 \le k \lt n$

計算量

• ならし $\textrm{O}(\alpha(n))$

---

Group

vector<vector<int>> Group()

• すべての連結成分に含まれる頂点の一覧を返します。

計算量

• ならし $\textrm{O}(n \alpha(n))$

---

Depends on

• Library/Common.hpp

Required by

• Kruskal - クラスカル法 (Library/Graph/Kruskal.hpp)

Verified with

• verify/AOJ-DSL-1-A.test.cpp
• verify/LC-MinimumSpanningTree.test.cpp
• verify/LC-Unionfind.test.cpp

Code

#pragma once

#include "../Common.hpp"

class UnionFind{
    public:
    UnionFind(size_t n) : data_(n, -1){}

    int Find(const int k){
        if(data_[k] < 0) return k;
        int r = Find(data_[k]);
        return data_[k] = r;
    }

    bool Same(const int x, const int y){
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    size_t Size(int k){
        int v = Find(k);
        return -data_[v];
    }

    vector<vector<int>> Group(){
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    private:
    vector<int> data_;
};

#line 2 "Library/DataStructure/UnionFind.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/DataStructure/UnionFind.hpp"

class UnionFind{
    public:
    UnionFind(size_t n) : data_(n, -1){}

    int Find(const int k){
        if(data_[k] < 0) return k;
        int r = Find(data_[k]);
        return data_[k] = r;
    }

    bool Same(const int x, const int y){
        return Find(x) == Find(y);
    }

    bool Unite(int x, int y){
        x = Find(x), y = Find(y);
        if(x == y) return false;
        if(data_[x] > data_[y]) swap(x, y);
        data_[x] += data_[y];
        data_[y] = x;
        return true;
    }
    
    size_t Size(int k){
        int v = Find(k);
        return -data_[v];
    }

    vector<vector<int>> Group(){
        vector<vector<int>> ret(data_.size());
        for(int i = 0; i < data_.size(); ++i){
            ret[Find(i)].emplace_back(i);
        }
        ret.erase(remove_if(begin(ret), end(ret), [&](vector<int> &v){
            return v.empty();
        }), end(ret));
        return ret;
    }

    private:
    vector<int> data_;
};

Back to top page