Pagini recente » Cod sursa (job #2667261) | Cod sursa (job #2666031) | Cod sursa (job #146430) | Cod sursa (job #667949) | Cod sursa (job #3297931)
#include <iostream>
#include <vector>
#include <queue>
const int NMAX = 1e5 + 5;
int n;
std::vector<int> adj[NMAX];
int main(void) {
#ifndef LOCAL
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
#endif
std::cin >> n;
for (int i = 0; i < n - 1; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::queue<int> bfs;
std::vector<bool> vis(n + 1, false);
std::vector<int> distances(n + 1, 0);
bfs.push(1);
while (!bfs.empty()) {
int curr = bfs.front();
vis[curr] = true;
bfs.pop();
for (auto &neigh : adj[curr]) {
if (!vis[neigh]) {
distances[neigh] = distances[curr] + 1;
bfs.push(neigh);
}
}
}
int furthest = -1;
int dist_max = -1;
for (int i = 1; i <= n; ++i) {
if (distances[i] > dist_max) {
dist_max = distances[i];
furthest = i;
}
}
distances.assign(distances.size(), 0);
vis.assign(vis.size(), false);
bfs.push(furthest);
while (!bfs.empty()) {
int curr = bfs.front();
vis[curr] = true;
bfs.pop();
for (auto &neigh : adj[curr]) {
if (!vis[neigh]) {
distances[neigh] = distances[curr] + 1;
bfs.push(neigh);
}
}
}
int dist_max_second = -1;
for (int i = 1; i <= n; ++i) {
if (distances[i] > dist_max_second) {
dist_max_second = distances[i];
}
}
std::cout << dist_max_second + 1 << '\n';
return 0;
}