Cod sursa(job #1592943)

Utilizator malina_floreaMalina Florea malina_florea Data 8 februarie 2016 10:34:00
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
#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 use[DMAX];
int lg[DMAX];

vector <int> lista[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].push_back(y);
        lista[y].push_back(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=0; i<lista[x].size(); i++)
        if (!use[lista[x][i]])
            DFS(lista[x][i], lungime+1);
}