Pagini recente » Cod sursa (job #1130762) | Cod sursa (job #1770780) | Istoria paginii runda/saptamana_altfel_6d/clasament | Cod sursa (job #1209789) | Cod sursa (job #1630555)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<vector<int> > G;
vector<int> D1, D2;
vector<bool> viz1, viz2;
int N, capatDiam2, capatDiam1, iCapatDiam1, iCapatDiam2;
void dfs(int nod, int d)
{
if(viz1[nod])
return;
D1[nod] = d;
viz1[nod] = 1;
if(d > capatDiam1){
capatDiam1 = d;
iCapatDiam1 = nod;
}
for(int i=0; i<G[nod].size(); ++i)
dfs(G[nod][i], d+1);
}
void dfs2(int nod, int d)
{
if(viz2[nod])
return;
viz2[nod] = 1;
D2[nod] = d;
if(d > capatDiam2){
capatDiam2 = d;
iCapatDiam2 = nod;
}
for(int i=0; i<G[nod].size(); ++i)
dfs2(G[nod][i], d+1);
}
int main()
{
freopen("darb.in", "rt", stdin);
freopen("darb.out", "wt", stdout);
scanf("%d", &N);
D1.assign(N+2, 0);
D2.assign(N+2, 0);
viz1.assign(N+2, 0);
viz2.assign(N+2, 0);
G.assign(N+1, vector<int>());
int x, y;
for(int i=1; i<N; ++i){
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 1);
dfs2(iCapatDiam1, 1);
cout<<capatDiam2<<'\n';
//cout<<iCapatDiam1<<' '<<iCapatDiam2;
return 0;
}