Cod sursa(job #1592928)

Utilizator malina_floreaMalina Florea malina_florea Data 8 februarie 2016 10:15:10
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#define DMAX 100005
using namespace std;
ifstream fin ("darb.in");
ofstream fout ("darb.out");

void citire();
void rez();
void DFS(int, int);

int n;
int lista[DMAX][DMAX];
int use[DMAX];
int lg[DMAX];

int main() {

    citire();
    rez();
    
    return 0;
}

void citire()
{
    int i, x, y;
    
    fin>> n;
    for (i=1; i<n; i++)
    {
        fin>> x>> y;
        lista[x][++lista[x][0]]=y;
        lista[y][++lista[y][0]]=x;
    }
}

void rez()
{
    int i, maxim, vfmax=1;
    
    DFS(1, 0);
    
    maxim=0;
    for (i=1; i<=n; i++)
        if (maxim<lg[i])
        {
            maxim=lg[i];
            vfmax=i;
        }
    
    for (i=1; i<=n; i++) use[i]=0;
    DFS(vfmax, 1);
    
    maxim = 0;
    for (i=1; i<=n; i++)
        if (maxim<lg[i])
            maxim=lg[i];
    
    fout<< maxim<< '\n';
}

void DFS(int x, int lungime)
{
    int i;
    
    lg[x]=lungime;
    use[x]=1;
    
    for (i=1; i<=lista[x][0]; i++)
        if (!use[lista[x][i]])
            DFS(lista[x][i], lungime+1);
}