This documentation is automatically generated by online-judge-tools/verification-helper
#include "algorithm/Graph/Tree/double_sweep.hpp"
木の直径を求めるアルゴリズム. ここで木の直径とは,「与えられた木における単純パスの長さの最大値」をいう. また,重みなし無向グラフに対しては,グラフの直径の下界となる.
アルゴリズムの流れは次の通り. ただし,$\operatorname{d}(u,v)$ はノード $u, v$ 間の距離,$\operatorname{ecc}(v)$ は $\max_u \operatorname{d}(v,u)$ を表す(”ecc” は “eccentricity” の略).
計算量は,木のノード数を $\lvert V \rvert$ とすると,$\mathcal{O}(\lvert V \rvert)$ となる.
アルゴリズムのポイントは,「木上の任意のノードから最も遠くにあるノードは直径の端点になる」ということ. アルゴリズムの正当性を背理法を用いて証明する.
ある木において,「根 $r$ から最も遠いノード $x$ は木の直径の端点にならない」と仮定する. また,木の直径の端点を $u, v$ とおく.
(1) まず,パス $r$-$x$ が直径 $u$-$v$ と交わる場合を考える. この交点となるノードを $h$ とおく. ノード $h$ は直径上にあるため,$h$ から最も離れているノードは $u$ または $v$ となる. しかし,根 $r$ から最も遠いノードは $x$ であり,$x$ は $u$ または $v$ のどちらかになるため,矛盾が生じる.
(2) 次に,パス $r$-$x$ が直径 $u$-$v$ と交わらない場合を考える. 直径上にある点を $h’$ とおく. $\operatorname{d}(r,h’) + \operatorname{d}(h’,x) \geq \operatorname{d}(r,x)$ であることに注意すると,
\[\begin{align} &\operatorname{d}(r,x) \geq \operatorname{d}(r,h') + \max(\operatorname{d}(h',u), \operatorname{d}(h',v)) \notag\\ \Rightarrow &\operatorname{d}(h',x) \geq \max(\operatorname{d}(h',u), \operatorname{d}(h',v)) \notag \end{align}\]となる.(1) と同様にノード $x$ は $u$ または $v$ のどちらかになるため,矛盾が生じる.
よって,木上の任意のノードから最も遠くにあるノードは直径の端点になることが示された.
#ifndef ALGORITHM_DOUBLE_SWEEP_HPP
#define ALGORITHM_DOUBLE_SWEEP_HPP 1
/**
* @brief Double Sweep(木の直径)
* @docs docs/Graph/Tree/double_sweep.md
*/
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace algorithm {
// 木の直径を求める.返り値は直径とその経路.O(|V|).
std::pair<int, std::vector<int> > double_sweep(const std::vector<std::vector<int> > &g, int s = 0) {
const int vn = g.size();
assert(0 <= s and s < vn);
int furthest_node;
std::vector<int> d(vn);
std::vector<int> pre(vn);
std::queue<int> que;
auto bfs = [&](int s) -> void {
std::fill(pre.begin(), pre.end(), -1);
d[s] = 0, pre[s] = -2;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
furthest_node = u;
for(int v : g[u]) {
assert(0 <= v and v < vn);
if(pre[v] != -1) continue;
d[v] = d[u] + 1, pre[v] = u;
que.push(v);
}
}
};
bfs(s);
bfs(furthest_node);
std::vector<int> path({furthest_node});
path.reserve(d[furthest_node] + 1);
for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
return {d[furthest_node], path}; // pair of (diameter, path).
}
// 重み付き木の直径を求める.返り値は直径とその経路.O(|V|).
template <typename Type>
std::pair<Type, std::vector<int> > double_sweep(const std::vector<std::vector<std::pair<int, Type> > > &g, int s = 0) {
const int vn = g.size();
assert(0 <= s and s < vn);
int furthest_node;
std::vector<Type> d(vn);
std::vector<int> pre(vn);
std::queue<int> que;
auto bfs = [&](int s) -> void {
furthest_node = s;
std::fill(pre.begin(), pre.end(), -1);
d[s] = 0, pre[s] = -2;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
if(d[u] > d[furthest_node]) furthest_node = u;
for(const auto &[v, cost] : g[u]) {
assert(0 <= v and v < vn);
if(pre[v] != -1) continue;
d[v] = d[u] + cost, pre[v] = u;
que.push(v);
}
}
};
bfs(s);
bfs(furthest_node);
std::vector<int> path({furthest_node});
for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
return {d[furthest_node], path}; // pair of (diameter, path).
}
} // namespace algorithm
#endif
#line 1 "algorithm/Graph/Tree/double_sweep.hpp"
/**
* @brief Double Sweep(木の直径)
* @docs docs/Graph/Tree/double_sweep.md
*/
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace algorithm {
// 木の直径を求める.返り値は直径とその経路.O(|V|).
std::pair<int, std::vector<int> > double_sweep(const std::vector<std::vector<int> > &g, int s = 0) {
const int vn = g.size();
assert(0 <= s and s < vn);
int furthest_node;
std::vector<int> d(vn);
std::vector<int> pre(vn);
std::queue<int> que;
auto bfs = [&](int s) -> void {
std::fill(pre.begin(), pre.end(), -1);
d[s] = 0, pre[s] = -2;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
furthest_node = u;
for(int v : g[u]) {
assert(0 <= v and v < vn);
if(pre[v] != -1) continue;
d[v] = d[u] + 1, pre[v] = u;
que.push(v);
}
}
};
bfs(s);
bfs(furthest_node);
std::vector<int> path({furthest_node});
path.reserve(d[furthest_node] + 1);
for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
return {d[furthest_node], path}; // pair of (diameter, path).
}
// 重み付き木の直径を求める.返り値は直径とその経路.O(|V|).
template <typename Type>
std::pair<Type, std::vector<int> > double_sweep(const std::vector<std::vector<std::pair<int, Type> > > &g, int s = 0) {
const int vn = g.size();
assert(0 <= s and s < vn);
int furthest_node;
std::vector<Type> d(vn);
std::vector<int> pre(vn);
std::queue<int> que;
auto bfs = [&](int s) -> void {
furthest_node = s;
std::fill(pre.begin(), pre.end(), -1);
d[s] = 0, pre[s] = -2;
que.push(s);
while(!que.empty()) {
int u = que.front();
que.pop();
if(d[u] > d[furthest_node]) furthest_node = u;
for(const auto &[v, cost] : g[u]) {
assert(0 <= v and v < vn);
if(pre[v] != -1) continue;
d[v] = d[u] + cost, pre[v] = u;
que.push(v);
}
}
};
bfs(s);
bfs(furthest_node);
std::vector<int> path({furthest_node});
for(int v = furthest_node; pre[v] != -2; v = pre[v]) path.push_back(pre[v]);
return {d[furthest_node], path}; // pair of (diameter, path).
}
} // namespace algorithm