Graphs

template <typename T>
struct Graph {
  struct Edge {
    int from;
    int to;
    T cost;
  };

  int n;
  std::vector<std::vector<int>> g;
  std::vector<Edge> edges;

  Graph(int _n) : n(_n) {
    g.resize(n);
  }

  virtual int addEdge(int from, int to, T cost) = 0;
};

template <typename T>
struct DiGraph : Graph<T> {
  using Graph<T>::n;
  using Graph<T>::g;
  using Graph<T>::edges;

  DiGraph(int _n) : Graph<T>(_n) {
    void(0);
  }

  [[maybe_unused]] int addEdge(int from, int to, T cost = 1) override {
    assert(0 <= from && from < n);
    int id = int(edges.size());
    g[from].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }

  [[nodiscard]] DiGraph<T> getReversed() const& {
    DiGraph<T> res(n);
    for (auto& e : edges) {
      res.add(e.to, e.from, e.cost);
    }
    return res;
  }
};

template <typename T>
struct UndiGraph : Graph<T> {
  using Graph<T>::n;
  using Graph<T>::g;
  using Graph<T>::edges;

  UndiGraph(int _n) : Graph<T>(_n) {
    void(0);
  }

  [[maybe_unused]] int addEdge(int from, int to, T cost = 1) override {
    assert(0 <= from && from < n);
    int id = int(edges.size());
    g[from].push_back(id);
    g[to].push_back(id);
    edges.push_back({from, to, cost});
    return id;
  }
};