Pagini recente » Cod sursa (job #273983) | Cod sursa (job #3275821) | Cod sursa (job #805659) | Cod sursa (job #276189) | Cod sursa (job #3295112)
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> adj;
vector<int> dist;
pair<int, int> bfs(int start_node, int n) {
fill(dist.begin(), dist.end(), -1);
queue<int> q;
dist[start_node] = 1;
q.push(start_node);
int farthest_node = start_node;
int max_dist = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
if (dist[v] > max_dist) {
max_dist = dist[v];
farthest_node = v;
}
}
}
}
return {farthest_node, max_dist};
}
int main() {
ifstream fin("darb.in");
ofstream fout("darb.out");
int n;
fin >> n;
adj.resize(n + 1);
dist.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
fin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
pair<int, int> result1 = bfs(1, n);
int endpoint1 = result1.first;
pair<int, int> result2 = bfs(endpoint1, n);
int diameter = result2.second;
fout << diameter << endl;
return 0;
}