Diameter(木の直径)
(graph/diameter.hpp)

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

説明

• グラフの直径を求める

vector<int> diameter(const Graph<T> &g)

Depends on

• Graph Template (graph/template.hpp)

Verified with

• test/yosupo/Tree/Tree-Diameter.test.cpp

Code

#include "template.hpp"

template <class T>
pair<T, vector<int>> diameter(const Graph<T> &g){
  const int n = g.size();
  vector<T> dist(n);
  vector<int> prev(n, -1);
  function<void(int,int)> dfs = [&](int pos, int par){
    for(auto &x : g[pos]) if(x != par){
      dist[x] = dist[pos] + x.cost;
      prev[x] = pos;
      dfs(x, pos);
    }
  };
  dfs(0, -1);
  int pos = max_element(dist.begin(), dist.end()) - dist.begin();
  dist.assign(n, 0); prev.assign(n, -1);
  dfs(pos, -1);
  pos = max_element(dist.begin(), dist.end()) - dist.begin();
  const T tot = dist[pos];
  vector<int> res;
  for(int i = pos; i != -1; i = prev[i]) res.push_back(i);
  return { tot, res };
}

#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>;
#line 2 "graph/diameter.hpp"

template <class T>
pair<T, vector<int>> diameter(const Graph<T> &g){
  const int n = g.size();
  vector<T> dist(n);
  vector<int> prev(n, -1);
  function<void(int,int)> dfs = [&](int pos, int par){
    for(auto &x : g[pos]) if(x != par){
      dist[x] = dist[pos] + x.cost;
      prev[x] = pos;
      dfs(x, pos);
    }
  };
  dfs(0, -1);
  int pos = max_element(dist.begin(), dist.end()) - dist.begin();
  dist.assign(n, 0); prev.assign(n, -1);
  dfs(pos, -1);
  pos = max_element(dist.begin(), dist.end()) - dist.begin();
  const T tot = dist[pos];
  vector<int> res;
  for(int i = pos; i != -1; i = prev[i]) res.push_back(i);
  return { tot, res };
}

Back to top page