src/graph/diameter.hpp

View this file on GitHub
Last update: 2022-12-24 16:49:35+09:00
Include: #include "src/graph/diameter.hpp"

Depends on

src/graph/template.hpp

Verified with

test/aoj/grl_5_a.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
using namespace std;

#include "./template.hpp"

template <typename T = long long> struct Diameter {
private:
  using P = pair<T, int>;
  int v;
  Graph<T> g;

public:
  Diameter(int v) : v(v), g(v) {}

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

  T calc() {
    P f = dfs(0, -1);
    P s = dfs(f.second, -1);
    return s.first;
  }

private:
  P dfs(int i, int parent) {
    P ret = make_pair((T)0, i);
    for (auto edge : g[i]) {
      if (edge.to == parent) {
        continue;
      }
      auto next = dfs(edge.to, i);
      next.first += edge.cost;
      ret = max(ret, next);
    }
    return ret;
  }
};

#line 2 "src/graph/diameter.hpp"

#include <bits/stdc++.h>
using namespace std;

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

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

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

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 7 "src/graph/diameter.hpp"

template <typename T = long long> struct Diameter {
private:
  using P = pair<T, int>;
  int v;
  Graph<T> g;

public:
  Diameter(int v) : v(v), g(v) {}

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

  T calc() {
    P f = dfs(0, -1);
    P s = dfs(f.second, -1);
    return s.first;
  }

private:
  P dfs(int i, int parent) {
    P ret = make_pair((T)0, i);
    for (auto edge : g[i]) {
      if (edge.to == parent) {
        continue;
      }
      auto next = dfs(edge.to, i);
      next.first += edge.cost;
      ret = max(ret, next);
    }
    return ret;
  }
};