UnionFind
(src/DataStructure/UnionFind.hpp)

• View this file on GitHub
• Last update: 2023-11-12 00:32:16+09:00
• Include: #include "src/DataStructure/UnionFind.hpp"

UnionFind

連結性の判定に使うデータ構造です。

コンストラクタ

UnionFind (int n)

計算量

$O(N)$

root(u)

頂点 $u$ が属するグループの根の番号を返します。

計算量

$O(\alpha(N))$

unite(u, v)

頂点 $u$ と $v$ を連結し、trueを返します。
すでに連結である場合はfalseを返します。

計算量

計算量は $O(\alpha(N))$

same(u, v)

頂点 $u$ と $v$ が連結である時trueを返し、そうでない時、falseを返します。
計算量は $O(\alpha(N))$ です。

size(u)

頂点 $u$ と連結な頂点の数を返します。
計算量は $O(\alpha(N))$ です。

Verified with

• test/DataStructure/UnionFind_unionfind.test.cpp

Code

#pragma once

#include <iostream>
#include <vector>

namespace lib{
    class UnionFind {
    public:
        std::vector<int> par, siz;
        UnionFind(int n) : par(n, -1), siz(n, 1) {}

        // 経路圧縮あり
        int root(int x) {
            if (par[x] == -1) return x;
            return par[x] = root(par[x]);
        }

        // 経路圧縮なし
        /*int root(int x){
            if(par[x] == -1) return x;
            return root(par[x]);
        } */

        bool unite(int x, int y) {
            int rx = root(x), ry = root(y);
            if (rx == ry) return false;
            if (size(rx) < size(ry)) std::swap(rx, ry);

            par[ry] = rx;
            siz[rx] += siz[ry];
            return true;
        }

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

        int size(int x) { return siz[root(x)]; }
    };
}

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

#include <iostream>
#include <vector>

namespace lib{
    class UnionFind {
    public:
        std::vector<int> par, siz;
        UnionFind(int n) : par(n, -1), siz(n, 1) {}

        // 経路圧縮あり
        int root(int x) {
            if (par[x] == -1) return x;
            return par[x] = root(par[x]);
        }

        // 経路圧縮なし
        /*int root(int x){
            if(par[x] == -1) return x;
            return root(par[x]);
        } */

        bool unite(int x, int y) {
            int rx = root(x), ry = root(y);
            if (rx == ry) return false;
            if (size(rx) < size(ry)) std::swap(rx, ry);

            par[ry] = rx;
            siz[rx] += siz[ry];
            return true;
        }

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

        int size(int x) { return siz[root(x)]; }
    };
}

Back to top page