Pagini recente » Cod sursa (job #1637941) | Cod sursa (job #342711) | Cod sursa (job #730195) | Cod sursa (job #2737231) | Cod sursa (job #2169502)
#include <iostream>
#include <fstream>
#include <cstring>
#define DMAX 100001
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
struct elem{
int val;
elem *urm;
}*v[DMAX];
int n;//date de intrare
int nivel[DMAX], frunza, opusFrunza;
void citire(){
in >> n;
for(int i = 1; i <= n; i++){
int a, b;
in >> a >> b;
elem *deAdaugat1 = new elem;
deAdaugat1 -> val = b;
deAdaugat1 -> urm = v[a];
v[a] = deAdaugat1;
elem *deAdaugat2 = new elem;
deAdaugat2 -> val = a;
deAdaugat2 -> urm = v[b];
v[b] = deAdaugat2;
}
}
void BF(int plec, int optiune){
memset(nivel, -1, sizeof(nivel));
int coada[DMAX], st, dr;
coada[1] = plec;
st = dr = 1;
nivel[plec] = 0;
while(st <= dr){
int varf = coada[st];
st++;
elem * parcurg = v[varf];
while(parcurg != NULL){
if(nivel[parcurg -> val] == -1){
coada[++dr] = parcurg -> val;
nivel[parcurg -> val] = nivel[varf] + 1;
}
parcurg = parcurg -> urm;
}
}
if(optiune == 0){
frunza = coada[dr];
}else{
opusFrunza = coada[dr];
}
}
void afisare(){
out << nivel[opusFrunza] + 1;//adaugam 1 pentru ca frunza se afla pe nivelul 0
//si nu intra la numaratoare
}
int main() {
citire();
BF(1, 0);// ma duc pe o frunza, caut o frunza
BF(frunza, 1);//de la frunza ma duc la nodul cel mai indepartat si astfel diametrul
afisare();
return 0;
}