Pagini recente » Monitorul de evaluare | Cod sursa (job #1230602) | Cod sursa (job #1501802) | Cod sursa (job #2771876) | Cod sursa (job #2812929)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define nmax 1000000
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n,d_distanta[nmax],visited[nmax],ultimul_element,diametru;
vector <int> graf[nmax];
queue <int> coada;
void bfs(int nod)
{
for(int i = 0; i <=n; i++)
{
visited[i] = 0;
d_distanta[i]=0;
}
///marcam ca vizitat nodul de plecare
visited[nod] = 1;
d_distanta[nod] = 1;
coada.push(nod);
while(!coada.empty())
{
int s = coada.front();
///luam pe rand toate elementele la care se poate ajunge din s si le adaugam in coada
vector<int>::iterator it;
for ( it = graf[s].begin(); it != graf[s].end(); ++it)
{
if (!visited[*it])
{
d_distanta[*it] = d_distanta[s] + 1; ///distanta va fi egala cu distanta tatalui +1
visited[*it] = 1;
coada.push(*it);
diametru=d_distanta[*it];
ultimul_element=*it;
}
}
coada.pop(); ///eliminam din coada nodul curent
}
/*for(int i=1;i<=n;i++)
cout<<d_distanta[i]<<" ";
*/
}
int main()
{int x,y;
fin>>n;
for(int i=1;i<n;i++)
{fin>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
bfs(1);
bfs(ultimul_element);
fout<<diametru;
return 0;
}