library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Diameter
(Graph/diameter.hpp)

• View this file on GitHub
• Last update: 2025-01-28 06:32:12+09:00
• Include: #include "Graph/diameter.hpp"

Code

#pragma once

template <typename T>
pair<T, vector<int>> Diameter(vector<vector<pair<int, T>>> &g) {
    int n = SZ(g);
    vector<T> dist(n, INF);
    queue<int> que;
    dist[0] = 0;
    que.push(0);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto &[to, c] : g[v])
            if (dist[to] == INF) {
                dist[to] = dist[v] + c;
                que.push(to);
            }
    }
    int v1 = -1;
    {
        T mx = -INF;
        rep(v, 0, n) if (chmax(mx, dist[v])) v1 = v;
    }
    dist.assign(n, INF);
    dist[v1] = 0;
    que.push(v1);
    vector<int> par(n);
    par[v1] = -1;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto &[to, c] : g[v])
            if (dist[to] == INF) {
                dist[to] = dist[v] + c;
                par[to] = v;
                que.push(to);
            }
    }
    int v2 = -1;
    T diam = -INF;
    rep(v, 0, n) if (chmax(diam, dist[v])) v2 = v;
    vector<int> path;
    int cur = v2;
    path.push_back(cur);
    while (cur != v1) {
        cur = par[cur];
        path.push_back(cur);
    }
    return {diam, path};
}

/**
 * @brief Diameter
 */

#line 2 "Graph/diameter.hpp"

template <typename T>
pair<T, vector<int>> Diameter(vector<vector<pair<int, T>>> &g) {
    int n = SZ(g);
    vector<T> dist(n, INF);
    queue<int> que;
    dist[0] = 0;
    que.push(0);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto &[to, c] : g[v])
            if (dist[to] == INF) {
                dist[to] = dist[v] + c;
                que.push(to);
            }
    }
    int v1 = -1;
    {
        T mx = -INF;
        rep(v, 0, n) if (chmax(mx, dist[v])) v1 = v;
    }
    dist.assign(n, INF);
    dist[v1] = 0;
    que.push(v1);
    vector<int> par(n);
    par[v1] = -1;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto &[to, c] : g[v])
            if (dist[to] == INF) {
                dist[to] = dist[v] + c;
                par[to] = v;
                que.push(to);
            }
    }
    int v2 = -1;
    T diam = -INF;
    rep(v, 0, n) if (chmax(diam, dist[v])) v2 = v;
    vector<int> path;
    int cur = v2;
    path.push_back(cur);
    while (cur != v1) {
        cur = par[cur];
        path.push_back(cur);
    }
    return {diam, path};
}

/**
 * @brief Diameter
 */

Back to top page