Cod sursa(job #2195795)

Utilizator alexandra.ioana.popaPopa Alexandra-Ioana alexandra.ioana.popa Data 17 aprilie 2018 13:28:36
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#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);
        }
}