圖的直徑
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?