graph/template.hpp

• View this file on GitHub
• Last update: 2021-08-01 23:46:19+09:00
• Include: #include "graph/template.hpp"

Required by

• BFS (graph/bfs.hpp)
• 01-BFS (graph/bin-bfs.hpp)
• Dijkstra (graph/dijkstra.hpp)
• グリッドグラフ (graph/grid-graph.hpp)
• LCA (最小共通祖先) (graph/lca.hpp)
• 最小全域木 (クラスカル法) (graph/mst-kruskal.hpp)
• 全方位木DP (ReRooting) (graph/rerooting.hpp)
• 強連結成分分解 (graph/strongly-connected-components.hpp)
• トポロジカルソート (graph/topological-sort.hpp)
• 木の直径 (graph/tree-diameter.hpp)
• warshall-floyd (graph/warshall-floyd.hpp)
• test/aoj/notest.GRL_4_B.cpp

Verified with

• test/aoj/ALDS_1_11_C.bfs.test.cpp
• test/aoj/ALDS_1_11_C.test.cpp
• test/aoj/GRL_1_A.test.cpp
• test/aoj/GRL_1_C.test.cpp
• test/aoj/GRL_2_A.test.cpp
• test/aoj/GRL_3_C.test.cpp
• 木の直径 (ReRooting) (test/aoj/GRL_5_A.rerooting.test.cpp)
• 木の直径のテスト (test/aoj/GRL_5_A.test.cpp)
• test/aoj/GRL_5_C.test.cpp

Code

#ifndef __GRAPH__TEMPLATE
#define __GRAPH__TEMPLATE

#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}

#endif // __GRAPH_TEMPLATE

#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}

Back to top page