getFarthestVertex(最遠頂点を求める)

romophic-library

用途

木において指定した頂点からもっとも遠い頂点を得る.

計算量

$ O(n) $

Depends

使い方

宣言

1
auto res = getFarthestVertex(g,s);

res.vで最も遠い頂点の頂点番号を得る. res.costで最も遠い頂点までの距離を得る.

実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct getFarthestVertex_return {
  int v, cost;
};
getFarthestVertex_return getFarthestVertex(DirectedGraph &_g, int _v) {
  queue<pair<int, int>> q;
  vector<int> t(_g.n, -1);
  q.push({_v, 0});
  getFarthestVertex_return res = {-1, -1};
  while (!q.empty()) {
    auto p = q.front();
    q.pop();
    bool tr = true;
    for (auto &i : _g.g[p.first])
      if (t[i.to] == -1) {
        tr = false;
        q.push({i.to, p.second + i.cost});
        t[i.to] = p.second + i.cost;
      }
    if (tr)
      res = {p.first, p.second};
  }
  return res;
}

Depended on

Verify👍

https://atcoder.jp/contests/typical90/submissions/57586680

Licensed under CC BY-NC-ND 4.0
All rights reserved.
Built with Hugo
Theme Stack is designed by Jimmy