グラフ構造体
(graph/graph_template.hpp)

• View this file on GitHub
• Last update: 2023-11-04 18:06:00+09:00
• Include: #include "graph/graph_template.hpp"

Required by

• graph/namori.hpp
• 区間に辺を張るテク (graph/range-edge-graph.hpp)
• 強連結成分分解(SCC) (graph/scc.hpp)
• BFS (graph/shortest-path/bfs.hpp)
• ダイクストラ法 (graph/shortest-path/dijkstra.hpp)
• トポロジカルソート (graph/topological-sort.hpp)
• 重心分解 (graph/tree/centroid-decomposition.hpp)
• 木の直径 (graph/tree/diameter.hpp)
• HL分解 (graph/tree/hld.hpp)
• 最小共通祖先(LCA) (graph/tree/lca.hpp)
• 木ハッシュ (graph/tree/tree-hash.hpp)
• 2-SAT (math/two_sat.hpp)

Verified with

• test/aoj/aoj2821.test.cpp
• test/library-checker/data-structure/vertex-add-path-sum.test.cpp
• test/library-checker/data-structure/vertex-add-subtree-sum.test.cpp
• test/library-checker/data-structure/vertex-set-path-composite.test.cpp
• test/library-checker/graph/scc.test.cpp
• test/library-checker/graph/shortest-path.test.cpp
• test/library-checker/math/two-sat.test.cpp
• test/library-checker/tree/lowest-common-ancestor.test.cpp
• test/library-checker/tree/lowest-common-ancestor2.test.cpp
• test/library-checker/tree/tree-diameter.test.cpp

Code

#pragma once

#include <cassert>
#include <vector>

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;

#line 2 "graph/graph_template.hpp"

#include <cassert>
#include <vector>

template <typename Cost = int> struct Edge {
    int from, to;
    Cost cost;
    int id;
    Edge() = default;
    explicit Edge(int from, int to, Cost cost = 1, int id = -1)
        : from(from), to(to), cost(cost), id(id) {}
    operator int() const { return to; }
};

template <typename Cost = int> class Graph {
  public:
    Graph() = default;
    explicit Graph(int N) : N(N), M(0), G(N) {}

    inline void add_directed_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M++);
    }

    inline void add_undirected_edge(int from, int to, Cost cost = 1) {
        assert(0 <= from && from < N);
        assert(0 <= to && to < N);
        G[from].emplace_back(from, to, cost, M);
        G[to].emplace_back(to, from, cost, M++);
    }

    inline size_t size() const { return G.size(); }
    inline std::vector<Edge<Cost>> &operator[](const int &i) { return G[i]; }
    inline const std::vector<Edge<Cost>> &operator[](const int &i) const {
        return G[i];
    }

  protected:
    int N, M;
    std::vector<std::vector<Edge<Cost>>> G;
};

template <class Cost = int> using Edges = std::vector<Edge<Cost>>;

Back to top page