Tree Diameter (木の直径)
(lib/graph/tree_diameter.hpp)

• View this file on GitHub
• Last update: 2024-07-07 17:27:42+09:00
• Include: #include "lib/graph/tree_diameter.hpp"

Tree Diameter (木の直径)

概要

木の直径を求めます。

最初は直径のパスを全て求める設計にしようと思いましたが、端点のみで妥協しています。

使い方

• TreeDiamiter(n): コンストラクタ (n は頂点数)
• add_edge(u, v): 頂点 $u$ から 頂点 $v$ に無向辺を追加します。
• build(): 重軽分解を行います。
• diameter(): 木の直径の長さを求めます（辺の本数）
• endpoint(): 木の直径の端の頂点を求めます。

計算量

頂点数を $V$ とします。

• TreeDiamiter(n): $\mathrm{O}(V)$
• add_edge(u, v): $\mathrm{O}(1)$
• build(): $\mathrm{O}(V)$
• diameter(): $\mathrm{O}(1)$
• endpoint(): $\mathrm{O}(1)$

Verified with

• test/aoj/grl/grl_5_a.test.cpp

Code

#pragma once

/**
 * @brief Tree Diameter (木の直径)
 * @docs docs/graph/tree_diameter.md
 */

template <typename T>
struct TreeDiameter{
    using Graph = vector<vector<pair<int, T>>>;
    Graph G;
    vector<T> dist, dist2;
    int V, root;
    T diam = -1;
    pair<int, int> ep;

    TreeDiameter(int n) : V(n){
        G.resize(n);
    }

    void add_edge(int u, int v, T w = 1){
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    void build(int _root = 0){
        root = _root;
        dist.assign(V, -1); dist2.assign(V, -1);
        dfs(G, root, -1, 0);
        T mx = 0;
        for(int i = 0; i < V; i++){
            if(mx < dist[i]){
                mx = dist[i];
                ep.first = i;
            }
        }

        dfs2(G, ep.first, -1, 0);
        for(int i = 0; i < V; i++){
            if(diam < dist2[i]){
                diam = dist2[i];
                ep.second = i;
            }
        }
    }

    void dfs(const Graph &G, int v, int p, T d){
        dist[v] = d;
        for(auto [e, w] : G[v]){
            if(e != p) dfs(G, e, v, d + w);
        }
    }

    void dfs2(const Graph &G, int v, int p, T d){
        dist2[v] = d;
        for(auto [e, w] : G[v]){
            if(e != p) dfs2(G, e, v, d + w);
        }
    }

    T diameter(){
        return diam;
    }

    pair<int, int> endpoint(){
        return ep;
    }
};

#line 2 "lib/graph/tree_diameter.hpp"

/**
 * @brief Tree Diameter (木の直径)
 * @docs docs/graph/tree_diameter.md
 */

template <typename T>
struct TreeDiameter{
    using Graph = vector<vector<pair<int, T>>>;
    Graph G;
    vector<T> dist, dist2;
    int V, root;
    T diam = -1;
    pair<int, int> ep;

    TreeDiameter(int n) : V(n){
        G.resize(n);
    }

    void add_edge(int u, int v, T w = 1){
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    void build(int _root = 0){
        root = _root;
        dist.assign(V, -1); dist2.assign(V, -1);
        dfs(G, root, -1, 0);
        T mx = 0;
        for(int i = 0; i < V; i++){
            if(mx < dist[i]){
                mx = dist[i];
                ep.first = i;
            }
        }

        dfs2(G, ep.first, -1, 0);
        for(int i = 0; i < V; i++){
            if(diam < dist2[i]){
                diam = dist2[i];
                ep.second = i;
            }
        }
    }

    void dfs(const Graph &G, int v, int p, T d){
        dist[v] = d;
        for(auto [e, w] : G[v]){
            if(e != p) dfs(G, e, v, d + w);
        }
    }

    void dfs2(const Graph &G, int v, int p, T d){
        dist2[v] = d;
        for(auto [e, w] : G[v]){
            if(e != p) dfs2(G, e, v, d + w);
        }
    }

    T diameter(){
        return diam;
    }

    pair<int, int> endpoint(){
        return ep;
    }
};

Back to top page