Graph Template(グラフテンプレート) (graph/graph-template.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2024-05-27 02:13:15+09:00
Include: #include "graph/graph-template.hpp"

Edge

辺を表す構造体です。

それぞれの Edge は以下の値を持ちます。

int from, to;
T cost;
int idx;

頂点 from から to を繋ぐ重み cost の辺があることを意味します。

idx は辺の番号です。特に指定しない場合は、辺が追加された順番に番号が割り当てられます。

コンストラクタ

Edge< T >(int from, int to, T cost = 1, int idx = -1)

頂点 from から to を結ぶ重み cost の辺を追加します。

T は辺の重みの型です。

int

operator int() const

to を返します。

Graph

グラフを隣接リストで表すための構造体です。

コンストラクタ

Graph< T >(int n)

頂点数 $n$ の空グラフを作ります。

T は辺の重みの型です。

計算量

$O(n)$

size

size_t size() const

頂点数を返します。

計算量

$O(1)$

add_directed_edge

void add_directed_edge(int from, int to, T cost = 1)

頂点 from から to を繋ぐ重み cost の有向辺を追加します。

制約

$0 \leq from, to \lt n$

計算量

$O(1)$

add_edge

void add_edge(int from, int to, T cost = 1)

頂点 from と to を繋ぐ重み cost の無向辺を追加します。

制約

$0 \leq from, to \lt n$
$from \neq to$

計算量

$O(1)$

read

void read(int M, int padding = -1, bool weighted = false, bool directed = false)

$M$ 本の辺を標準入力 cin から読み込みます。

入力で与えられた頂点番号に padding を加算します。

weighted = false のとき重みなしのグラフ、true のとき重みつきのグラフを意味します。

directed = false のとき無向グラフ、true のとき有向グラフを意味します。

詳細は実際の実装を参照してください。

計算量

$O(M)$

operator[]

(1) vector<Edge<T> > &operator[](int k)
(2) const vector<Edge<T> > &operator[](int k) const

頂点 $k$ から生えるすべての辺を返します。

制約

$0 \leq k \lt n$

計算量

$O(1)$

Required by

Verified with

Code

#pragma once

template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;

#line 2 "graph/graph-template.hpp"

template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;