Graph Template
(graph/template.hpp)

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "graph/template.hpp"

Required by

• data-structure/HLD.hpp
• Bellman Ford法 (graph/bellman-ford.hpp)
• 木の中心 (graph/center.hpp)
• graph/check-bipartite.hpp
• Cycle Detect(サイクル検出) (graph/cycle-detect.hpp)
• Diameter(木の直径) (graph/diameter.hpp)
• graph/dijkstra.hpp
• graph/dinic.hpp

Verified with

• test/aoj/GRL/GRL_1_B.test.cpp
• test/aoj/GRL/GRL_2_A.test.cpp
• test/aoj/GRL/GRL_6_A2.test.cpp
• test/yosupo/Data-Structure/Vertex-Add-Path-Sum.test.cpp
• test/yosupo/Data-Structure/Vertex-Set-Path-Composite.test.cpp
• test/yosupo/Graph/Cycle-Detection(Directed).test.cpp
• test/yosupo/Graph/Shortest-Path.test.cpp
• test/yosupo/Tree/Tree-Diameter.test.cpp

Code

#pragma once

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;

#line 2 "graph/template.hpp"

/**
 * @brief Graph Template
*/
template <class T>
struct Edge {
  int from,to;
  T cost;
  int idx;
  Edge(){};
  Edge(int f, int t, T c=1, int i=-1) : from(f), to(t), cost(c), idx(i){}
  Edge(int t) : to(t), from(-1), cost(1), idx(-1){}
  operator int() const{ return to; }
  bool operator<(const Edge &e){ return cost < e.cost; }
};
template <class T>
struct Graph : vector<vector<Edge<T>>> {
  Graph(){}
  Graph(const int &n) : vector<vector<Edge<T>>>(n){}
  void add_edge(int a, int b, T c=1, int i=-1){
    (*this)[a].push_back({ a, b, c, i });
  }
};
using graph = Graph<int>;

Back to top page