ei1333's page

ホーム > Wiki

木の直径

説明

非負の重み付き無向木の直径を求める。適当な頂点 $s$ から最も遠い頂点 $u$ を求める。次に $u$ から最も遠い頂点 $v$ を求める。このとき、($u$, $v$) が最遠頂点対であり、すなわち木の直径である。

計算量

$O(E)$

実装例

struct edge
{ 
  int to, cost;
};
typedef vector< vector< edge > > Graph;

pair< int, int > dfs(const Graph& graph, int idx, int prev)
{
  pair< int, int > ret = make_pair(0, -1);
  for(int i = 0; i < graph[idx].size(); i++) {
    if(graph[idx][i].to != prev){
      pair< int, int > cost = dfs(graph, graph[idx][i].to, idx);
      cost.first += graph[idx][i].cost;
      ret = max(ret, cost);
    }
  }
  return(ret);
}
int Diameter(Graph& tree)
{
  pair< int, int > p = dfs(tree, 0, -1);
  pair< int, int > q = dfs(tree, p.second, -1);
  return(q.first);
}

問題例