無向グラフの連結成分分解
(Src/Graph/Components/ConnectedComponents.hpp)

• View this file on GitHub
• Last update: 2023-07-19 15:15:04+09:00
• Include: #include "Src/Graph/Components/ConnectedComponents.hpp"

概要

無向グラフ $G = (V, E)$ を構築し、各頂点、各辺がどの連結成分に属するかを管理します。

ライブラリの使い方

コンストラクタ

ConnectedComponents(usize n)

$V$ を $V = \{ 0, 1, \dots, n - 1 \}$ で初期化する。この時点で辺は存在していないものとする。

計算量: $O(n)$

addEdge

void addEdge(u32 u, u32 v)

無向辺 $(u, v)$ を追加する。

制約:

• $0\ \le\ u, v\ <\ \mid V\mid$
• 以前にbuildを呼び出していないこと

計算量: ならし定数時間

edge

Edge edge(u32 e) const

$e$ 番目に追加された辺を返す。

返り値のEdgeは以下のようなclassです。

class Edge {
public:
    inline u32 u() const noexcept // 辺の端点の頂点を返す。
    inline u32 v() const noexcept // uとは別の端点の頂点を返す。
    inline u32 id() const noexcept // edgeの引数eを返す。
};

制約: $0\ \le\ e\ <\ \mid E\mid$ (addEdgeを呼び出した回数よりも小さい値であること)

計算量: 定数時間

build

void build()

現在の $(V, E)$ について各頂点、各辺を連結成分毎に番号を振り分ける。

連結成分の番号は以下のルールで決められる。

1. 頂点 $0$ を含む連結成分を $0$ 番とする
2. $0$ 番目から $i - 1$ 番目の連結成分に属していない頂点の中で、番号が最小の頂点を $v$ とする。 $v$ が含まれる連結成分を $i$ 番とする

制約: buildをそれ以前に呼び出していない

計算量: $O(\mid V\mid + \mid E\mid)$

(複数回buildを呼び出さないといけないような状況ではdisjoint set unionを使うべきだと考えているため、buildを一度しか呼び出せないようにしています。不都合が生じた場合、修正します。)

size

inline usize size() const noexcept

連結成分の数を返す。

制約: buildを既に呼び出している

計算量: 定数時間

n

(1) inline usize n() const noexcept
(2) inline usize n(u32 c) const noexcept

(1) 頂点数 $\mid V\mid$ を返す

計算量: 定数時間

(2) $c$ 番目の連結成分の頂点数を返す

制約:

• buildを既に呼び出している
• $c$ は連結成分の数より小さい整数である

計算量: 定数時間

m

(1) inline usize m() const noexcept
(2) inline usize m(u32 c) const noexcept

(1) 辺数 $\mid E\mid$ を返す(addEdgeが呼び出された回数)

計算量: 定数時間

(2) $c$ 番目の連結成分の辺数を返す

制約:

• buildを既に呼び出している
• $c$ は連結成分の数より小さい整数である

計算量: 定数時間

operator[]

inline u32 operator[](const u32 v) const noexcept

頂点 $v$ を含む連結成分の番号を返す。

制約:

• buildを既に呼び出している
• $0\ \le\ v\ <\ \mid V\mid$

計算量: 定数時間

indexV

inline u32 indexV(u32 v) const noexcept

operator[]と同じ

indexE

inline u32 indexE(u32 e) const noexcept

$e$ 番目に追加された辺を含む連結成分の番号を返す。

制約:

• buildを既に呼び出している
• $0\ \le\ e\ <\ \mid E\mid$

計算量: 定数時間

same

inline bool same(u32 u, u32 v) const noexcept

頂点 $u, v$ が同じ連結成分に属しているならtrue、そうで無い時falseを返す。

制約

• buildを既に呼び出している
• $0\ \le\ u, v\ <\ \mid V\mid$

vs

inline const std::vector<u32>& vs(u32 c) const noexcept

c番目の連結成分が属する頂点の列を返します。返り値の列は頂点番号に対して昇順に並んでいます。

制約

• buildを既に呼び出している
• cは連結成分の数より小さい整数

計算量: 連結成分に含まれる頂点数に比例する

es

inline const std::vector<u32>& es(u32 c) const noexcept

c番目の連結成分が属する辺の列を返します。それぞれの辺の追加された番号のみを返します。

制約

• buildを既に呼び出している
• cは連結成分の数より小さい整数

計算量: 連結成分に含まれる辺数に比例する

hasCycle

inline bool hasCycle(u32 c) const

c番目の連結成分がサイクルを有しているか判定します。

自己ループや多重辺もサイクルとみなしていることに注意してください。

制約

• buildを既に呼び出している
• cは連結成分の数より小さい整数

計算量: 定数時間

アルゴリズム

DFS(Depth First Search)によって実装されています。

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AOJ/ALDS1_11_D.test.cpp
• Test/AtCoder/abc247_f.test.cpp
• Test/AtCoder/abc288_c.test.cpp
• Test/AtCoder/abc292_d.test.cpp
• Test/AtCoder/abc293_d.test.cpp
• Test/AtCoder/abc334_g.test.cpp

Code

#pragma once

#include "../../Template/TypeAlias.hpp"

#include <limits>
#include <vector>
#include <utility>
#include <stack>
#include <algorithm>
#include <cassert>

namespace zawa {

class ConnectedComponents {
public:
    struct Edge {
    private:
        u32 u_, v_, id_;
    public:
        Edge(u32 u, u32 v, u32 id) : u_{ u }, v_{ v }, id_{ id } {}

        inline u32 u() const noexcept {
            return u_;
        }
        inline u32 v() const noexcept {
            return v_;
        }
        inline u32 id() const noexcept {
            return id_;
        }
    };

private:
    class Component {
    private:
        std::vector<u32> vs_, es_;
    public:
        Component() = default;
        Component(const std::vector<u32>& vs, const std::vector<u32>& es) : vs_{ vs }, es_{ es } {
            vs_.shrink_to_fit();
            es_.shrink_to_fit();
        }
        
        inline usize n() const noexcept {
            return vs_.size();
        }
        inline usize m() const noexcept {
            return es_.size();
        }
        const std::vector<u32>& vs() const noexcept {
            return vs_;
        }
        const std::vector<u32>& es() const noexcept {
            return es_;
        }
        bool hasCycle() const {
            return not (n() == m() + 1);
        }
    };

    constexpr static u32 INVALID_{ std::numeric_limits<u32>::max() };

    std::vector<std::vector<u32>> graph_;
    std::vector<std::pair<u32, u32>> edges_;

    std::vector<u32> indexV_, indexE_;
    std::vector<Component> components_;

    bool isBuilt;

    void dfs(u32 s) {
        indexV_[s] = components_.size();
        std::stack<u32> stk{ { s } };
        while (stk.size()) {
            u32 v{ stk.top() };
            stk.pop();
            for (auto x : graph_[v]) {
                if (indexV_[x] == INVALID_) {
                    indexV_[x] = components_.size();
                    stk.push(x);
                }
            }
        }
    }

    void buildComponents() {
        std::vector<std::vector<u32>> vs(components_.size()), es(components_.size());
        for (u32 v{} ; v < n() ; v++) {
            vs[indexV_[v]].emplace_back(v);
        }
        for (u32 e{} ; e < m() ; e++) {
            es[indexE_[e]].emplace_back(e);
        }
        for (u32 i{} ; i < components_.size() ; i++) {
            components_[i] = Component(vs[i], es[i]);
        }
        components_.shrink_to_fit();
    }

public:
    ConnectedComponents() = default;

    ConnectedComponents(usize n) 
        : graph_(n), edges_{}, indexV_(n, INVALID_), indexE_{}, components_{}, isBuilt{} {
        graph_.shrink_to_fit();
    }
    
    void addEdge(u32 u, u32 v) {
        assert(not isBuilt);
        graph_[u].emplace_back(v);
        graph_[v].emplace_back(u);
        edges_.emplace_back(u, v);
    }

    inline usize n() const noexcept {
        return graph_.size();
    }

    inline usize m() const noexcept {
        return edges_.size();
    }

    Edge edge(u32 e) const {
        assert(e < m());
        return Edge{ edges_[e].first, edges_[e].second, e };
    }

    void build() {
        assert(not isBuilt);
        edges_.shrink_to_fit();
        indexV_.shrink_to_fit();
        for (u32 v{} ; v < n() ; v++) {
            if (indexV_[v] == INVALID_) {
                dfs(v);
                components_.emplace_back();
            }
        }
        indexE_.resize(m());
        indexE_.shrink_to_fit();
        for (u32 e{} ; e < m() ; e++) {
            indexE_[e] = indexV_[edges_[e].first];
        }
        buildComponents();
        isBuilt = true;
    }

    inline u32 operator[](const u32 v) const noexcept {
        assert(isBuilt);
        assert(v < n());
        return indexV_[v];
    }

    inline u32 indexV(u32 v) const noexcept {
        assert(isBuilt);
        assert(v < n());
        return indexV_[v];
    }

    inline u32 indexE(u32 e) const noexcept {
        assert(isBuilt);
        assert(e < m());
        return indexE_[e];
    }

    inline bool same(u32 u, u32 v) const noexcept {
        assert(isBuilt);
        assert(u < n());
        assert(v < n());
        return indexV_[u] == indexV_[v];
    }

    inline usize size() const noexcept {
        assert(isBuilt);
        return components_.size();
    }

    inline usize n(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].n();
    }

    inline const std::vector<u32>& vs(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].vs();
    }

    inline usize m(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].m();
    }

    inline const std::vector<u32>& es(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].es();
    }

    inline bool hasCycle(u32 c) const {
        assert(isBuilt);
        assert(c < size());
        return components_[c].hasCycle();
    }

};

} // namespace zawa

#line 2 "Src/Graph/Components/ConnectedComponents.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Components/ConnectedComponents.hpp"

#include <limits>
#include <vector>
#include <utility>
#include <stack>
#include <algorithm>
#include <cassert>

namespace zawa {

class ConnectedComponents {
public:
    struct Edge {
    private:
        u32 u_, v_, id_;
    public:
        Edge(u32 u, u32 v, u32 id) : u_{ u }, v_{ v }, id_{ id } {}

        inline u32 u() const noexcept {
            return u_;
        }
        inline u32 v() const noexcept {
            return v_;
        }
        inline u32 id() const noexcept {
            return id_;
        }
    };

private:
    class Component {
    private:
        std::vector<u32> vs_, es_;
    public:
        Component() = default;
        Component(const std::vector<u32>& vs, const std::vector<u32>& es) : vs_{ vs }, es_{ es } {
            vs_.shrink_to_fit();
            es_.shrink_to_fit();
        }
        
        inline usize n() const noexcept {
            return vs_.size();
        }
        inline usize m() const noexcept {
            return es_.size();
        }
        const std::vector<u32>& vs() const noexcept {
            return vs_;
        }
        const std::vector<u32>& es() const noexcept {
            return es_;
        }
        bool hasCycle() const {
            return not (n() == m() + 1);
        }
    };

    constexpr static u32 INVALID_{ std::numeric_limits<u32>::max() };

    std::vector<std::vector<u32>> graph_;
    std::vector<std::pair<u32, u32>> edges_;

    std::vector<u32> indexV_, indexE_;
    std::vector<Component> components_;

    bool isBuilt;

    void dfs(u32 s) {
        indexV_[s] = components_.size();
        std::stack<u32> stk{ { s } };
        while (stk.size()) {
            u32 v{ stk.top() };
            stk.pop();
            for (auto x : graph_[v]) {
                if (indexV_[x] == INVALID_) {
                    indexV_[x] = components_.size();
                    stk.push(x);
                }
            }
        }
    }

    void buildComponents() {
        std::vector<std::vector<u32>> vs(components_.size()), es(components_.size());
        for (u32 v{} ; v < n() ; v++) {
            vs[indexV_[v]].emplace_back(v);
        }
        for (u32 e{} ; e < m() ; e++) {
            es[indexE_[e]].emplace_back(e);
        }
        for (u32 i{} ; i < components_.size() ; i++) {
            components_[i] = Component(vs[i], es[i]);
        }
        components_.shrink_to_fit();
    }

public:
    ConnectedComponents() = default;

    ConnectedComponents(usize n) 
        : graph_(n), edges_{}, indexV_(n, INVALID_), indexE_{}, components_{}, isBuilt{} {
        graph_.shrink_to_fit();
    }
    
    void addEdge(u32 u, u32 v) {
        assert(not isBuilt);
        graph_[u].emplace_back(v);
        graph_[v].emplace_back(u);
        edges_.emplace_back(u, v);
    }

    inline usize n() const noexcept {
        return graph_.size();
    }

    inline usize m() const noexcept {
        return edges_.size();
    }

    Edge edge(u32 e) const {
        assert(e < m());
        return Edge{ edges_[e].first, edges_[e].second, e };
    }

    void build() {
        assert(not isBuilt);
        edges_.shrink_to_fit();
        indexV_.shrink_to_fit();
        for (u32 v{} ; v < n() ; v++) {
            if (indexV_[v] == INVALID_) {
                dfs(v);
                components_.emplace_back();
            }
        }
        indexE_.resize(m());
        indexE_.shrink_to_fit();
        for (u32 e{} ; e < m() ; e++) {
            indexE_[e] = indexV_[edges_[e].first];
        }
        buildComponents();
        isBuilt = true;
    }

    inline u32 operator[](const u32 v) const noexcept {
        assert(isBuilt);
        assert(v < n());
        return indexV_[v];
    }

    inline u32 indexV(u32 v) const noexcept {
        assert(isBuilt);
        assert(v < n());
        return indexV_[v];
    }

    inline u32 indexE(u32 e) const noexcept {
        assert(isBuilt);
        assert(e < m());
        return indexE_[e];
    }

    inline bool same(u32 u, u32 v) const noexcept {
        assert(isBuilt);
        assert(u < n());
        assert(v < n());
        return indexV_[u] == indexV_[v];
    }

    inline usize size() const noexcept {
        assert(isBuilt);
        return components_.size();
    }

    inline usize n(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].n();
    }

    inline const std::vector<u32>& vs(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].vs();
    }

    inline usize m(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].m();
    }

    inline const std::vector<u32>& es(u32 c) const noexcept {
        assert(isBuilt);
        assert(c < size());
        return components_[c].es();
    }

    inline bool hasCycle(u32 c) const {
        assert(isBuilt);
        assert(c < size());
        return components_[c].hasCycle();
    }

};

} // namespace zawa

Back to top page