Pagini recente » Cod sursa (job #854415) | Cod sursa (job #1268109) | Cod sursa (job #101430) | Cod sursa (job #2805973) | Cod sursa (job #2195795)
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> L[NMAX];
int n;
void citire();
void dfs(int start);
bool uz[NMAX];
int lg[NMAX];
int main()
{int maxim=0, i, poz;
citire();
//facem dfs pentru orice varf; vedem pe ce nivel se afla fiecare dintre varfuri
dfs(1);
//vedem care e cea mai indepartata frunza
for (i=1; i<=n; i++) //n varfuri, atentie;
if (lg[i]>maxim)
{
maxim=lg[i];
poz=i;
}
//am gasit frunza cea mai indepartata de primul varf;
//initializam vectorii lg si uz;
for (i=1; i<=n; i++)
{
lg[i]=0;
uz[i]=0;
}
lg[poz]=1;
dfs(poz); //gasim frunza cea mai indepartata de varful i;
maxim=0;
for (i=1; i<=n; i++)
if (lg[i]>maxim)
maxim=lg[i];
fout<<maxim;
return 0;
}
void dfs(int start)
{
//aflam lungimea listei de adiacenta a lui start;
int n=L[start].size();
int i;
uz[start]=1; //am vizitat varful asta;
for (i=0; i<n; i++)
//vizitam fiecare varf nevizitat;
if (uz[L[start][i]]==0) //adica daca nu am vizitat vecinul i al lui start
{
lg[L[start][i]]=lg[start]+1;
dfs(L[start][i]);
}
}
void citire()
{int i, x, y;
fin>>n; //n noduri
for (i=1; i<n; i++) //n-1 muchii
{
fin>>x>>y;
L[y].push_back(x);
L[x].push_back(y);
}
}