Pagini recente » Cod sursa (job #2907904) | Cod sursa (job #572602) | Borderou de evaluare (job #1321186) | Cod sursa (job #646286) | Cod sursa (job #3339166)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector< int > v[100002]; // lista de vecini
// vf vecin
int d1[100002], d2[100000];
queue <int> q;
void bfs(int x, int d[]){
// d[i]==0 pt i nu stim distanta
q.push(x); d[x]=1;
while ( !q.empty() ){
int vf = q.front(); q.pop();
int l = v[vf].size();
for(int i = 0; i <l; i++){
if(d[v[vf][i] ] == 0 ){ // vf---------v[vf][i]
q.push(v[vf][i]);
d[v[vf][i]] = d[vf]+1;
}
}
}
// q este vida
}
int main()
{
int n, a, b;
fin>>n;
for(int i=1;i<=n-1;i++){
fin>>a>>b; // a------b
v[a].push_back( b );
v[b].push_back( a );
}
bfs(1,d1); // d1[i]= dist minim a de la 1 la i
// gasesc y cu d1[y] maxim
int y=1;
for(int i=1;i<=n;i++){
if(d1[i]>d1[y]){
y=i;
}
}
bfs(y, d2); // d2[i]= dist minim de la y la i
// maxim din vectorul d2
int diam=0;
for(int i=1;i<=n;i++){
diam=max(diam, d2[i]);
}
fout<<diam;
return 0;
}