圖的直徑

a 到 b 的距離

圖的直徑 (求圖中兩點最遠的距離)

/*
 * b967. 4. 血緣關係
 * C++
 * AC (0.2s, 10.9MB)
*/
#include <bits/stdc++.h>
using namespace std;

pair<int, int> bfs(const vector<vector<int>>& g, int s) {
    queue<int> q;
    unordered_map<int, int> levels;
    q.push(s);
    levels[s] = 0;
    //
    while (!q.empty()) {
        int n = q.front();
        q.pop();
        int l = levels[n];
        for(int i=0;i<g[n].size();i++) {
            int x = g[n][i];
            if (levels.find(x)==levels.end()) {
                levels[x] = l+1;
                q.push(x);
            }
        }
    }
    //
    int ml = -1;
    int mn = -1;
    for (const auto& pair : levels) {
        if (pair.second > ml) {
            ml = pair.second;
            mn = pair.first;
        }
    }
    return {mn,ml};
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    //無向圖
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cout << bfs(g, bfs(g, 0).first).second << endl; //用最遠的點 bfs 來求最遠的距離
    return 0;
}

Last updated

Was this helpful?