木の中心
(graph/center.hpp)

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

説明

• 木の中心を求める

vector<int> find_centor(const graph &g)

Depends on

• Graph Template (graph/template.hpp)

Code

#include "template.hpp"
#include <functional>

template <class graph>
pair<vector<int>, int> find_centor(const graph &g){
  const int n = g.size();
  vector<int> dist(n), prev(n, -1);
  function<void(int,int)> dfs = [&](int pos, int par){
    for(const auto &x : g[pos]) if(x != par){
      dist[x] = dist[pos] + 1;
      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 int longest = dist[pos];
  int max_dist = longest;
  vector<int> res;
  for(int i = pos; i != -1; i = prev[i]){
    if(max_dist == longest/2 || max_dist == (longest+1)/2) res.push_back(i);
    max_dist--;
  }
  return { res, longest };
}

#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/center.hpp"
#include <functional>

template <class graph>
pair<vector<int>, int> find_centor(const graph &g){
  const int n = g.size();
  vector<int> dist(n), prev(n, -1);
  function<void(int,int)> dfs = [&](int pos, int par){
    for(const auto &x : g[pos]) if(x != par){
      dist[x] = dist[pos] + 1;
      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 int longest = dist[pos];
  int max_dist = longest;
  vector<int> res;
  for(int i = pos; i != -1; i = prev[i]){
    if(max_dist == longest/2 || max_dist == (longest+1)/2) res.push_back(i);
    max_dist--;
  }
  return { res, longest };
}

Back to top page