Pagini recente » Cod sursa (job #541410) | Cod sursa (job #849422) | Cod sursa (job #1742609) | Cod sursa (job #768792) | Cod sursa (job #3230282)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
void bfs(int source, std::vector<std::vector<int>> &adj, std::vector<int> &d)
{
std::queue<int> q;
for (auto &dist : d)
dist = -1;
d[source] = 0;
q.push(source);
while (!q.empty()) {
auto node = q.front();
q.pop();
for (auto neigh : adj[node]) {
if (d[neigh] == -1) {
d[neigh] = d[node] + 1;
q.push(neigh);
}
}
}
}
int main()
{
std::ifstream fin("darb.in");
std::ofstream fout("darb.out");
int n, second_source, diam;
std::vector<std::vector<int>> adj;
std::vector<int> d;
fin >> n;
adj.resize(n);
d.resize(n);
for (int v, w, i = 0; i < n - 1; ++i) {
fin >> v >> w;
adj[v - 1].push_back(w - 1);
adj[w - 1].push_back(v - 1);
}
bfs(0, adj, d);
second_source = 0;
for (int v = 1; v < n; ++v)
if (d[v] > d[second_source])
second_source = v;
bfs(second_source, adj, d);
diam = 0;
for (int v = 0; v < n; ++v)
diam = std::max(diam, d[v]);
fout << diam + 1 << '\n';
fin.close();
fout.close();
return 0;
}