Pagini recente » Istoria paginii runda/pregatire_oni_baraj_juniori/clasament | Cod sursa (job #1374928) | Cod sursa (job #431276) | Istoria paginii runda/cosmin_oni2018z2/clasament | Cod sursa (job #2632736)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
const int NMAX = 100'001;
int n, beenThere[NMAX] , depth[NMAX] , dist[NMAX];
vector <int> ARB[NMAX];
void Read() {
f >> n;
for(int i = 1;i <= n - 1;++i) {
int x, y;
f >> x >> y;
ARB[x].push_back(y);
ARB[y].push_back(x);
}
}
void dfs(int node) {
beenThere[node] = 1;
for (int neighbor : ARB[node]) {
if (!beenThere[neighbor]) {
depth[neighbor] = 1 + depth[node];
dfs(neighbor);
}
}
}
void bfs(const int& startNode) {
dist[startNode] = 1;
vector<bool> vis(n + 1,false);
queue <int> q;
q.push(startNode);
vis[startNode] = 1;
while(!q.empty()) {
int node = q.front();
q.pop();
for(int neighbor : ARB[node]) {
if (!vis[neighbor]) {
vis[neighbor] = 1;
dist[neighbor] = 1 + dist[node];
q.push(neighbor);
}
}
}
}
void print() {
int sol{};
for(int i = 1;i <= n;++i)
if(dist[i] > sol)
sol = dist[i];
g << sol << '\n';
}
void solve() {
dfs(1);
int max_depth_node {};
for(int i = 1;i <= n;++i)
if(depth[i] > depth[max_depth_node])
max_depth_node = i;
bfs(max_depth_node);
}
int main() {
Read();
solve();
print();
return 0;
}