Pagini recente » Cod sursa (job #33438) | Cod sursa (job #2507769) | Cod sursa (job #1642343) | Cod sursa (job #360849) | Cod sursa (job #2796874)
/*
Diametrul unui arbore
Diametrul unui arbore reprezintă lungimea drumului (ca numar de noduri) intre cele mai departate două frunze.
Cerinţă
Dându-se un arbore cu N noduri, să se determine diametrul acestuia.
Date de intrare
Pe prima linie a fisierului darb.in se afla N cu specificatiile de mai sus. Pe următoarele N-1 linii se află cate o pereche de numere a si b reprezentând muchiile arborelui.
Date de ieşire
În fişierul de ieşire darb.out se va afisa diametrul arborelui.
Restricţii
2 ≤ N ≤ 100.000
*/
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define NMAX 100005
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
vector < int > v[NMAX];
int nrmax, j;
void dfs1(int x, int prec, int nr);
void dfs2(int x, int prec, int nr);
int main()
{
int n, x, y;
fin >> n;
while(n--)
{
fin >> x >> y;
v[x].pb(y), v[y].pb(x);
}
dfs1(1, 0, 1);
dfs2(j, 0, 1);
fout << nrmax;
return 0;
}
void dfs1(int x, int prec, int nr)
{
if(nr > nrmax) nrmax = nr, j = x;
for(auto it:v[x]) if(it != prec) dfs1(it, x, nr + 1);
}
void dfs2(int x, int prec, int nr)
{
if(nr > nrmax) nrmax = nr;
for(auto it:v[x]) if(it != prec) dfs2(it, x, nr + 1);
}
/*
IN:
11
1 2
1 3
1 4
2 5
3 6
4 7
5 8
5 9
6 10
10 11
OUT:
8
*/