Cod sursa(job #2407246)

Utilizator VladieftimieVlad Enia Vladieftimie Data 16 aprilie 2019 18:29:20
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

int df(int a[][100000],int n,int d[],int x)
{
    for(int i=1;i<=n;i++)
        if(a[x][i] && d[i]==-1)
        {
            d[i]=d[x]+1;
            df(a,n,d,i);
        }
}

int a[100000][100000];

int main()
{
    int d[100000],x,y,n,vf1,vf2,maxi=-1;                   ///vectorul d reprezinta vectorul de distante dintr-un anumit nod si toate celelalte;
    fin>>n;
    for(int i=1;i<=n;i++)
        d[i]=-1;                                        ///asftel, vom initializa acest vector cu -1, pentru ca 0 va fi distanta de la acel nod la el insusi;
    d[1]=0;

    for(int i=1;i<n;i++)
    {
        fin>>x>>y;
        a[x][y]=a[y][x]=1;                              ///cream matricea de adiacenta a grafului;
    }

    df(a,n,d,1);                                        ///parcurgem in adancime graful dintr-un nod oarecare, in acest caz 1;

    for(int i=1;i<=n;i++)
        if(d[i]>maxi)
        {
            maxi=d[i];
            vf2=i;                                      ///vom retine nodul cel mai indepartat de nodul 1, acesta fiind unul din varfurile celui mai lung lant;
        }

    for(int i=1;i<=n;i++)                               ///deoarece dorim sa mai facem o parcurgere in adancime din varful gasit mai sus, vom reinitializa vectorul cu -1, si cu 0 pe pozitia acelui varf;
        d[i]=-1;
    d[vf2]=0;
    maxi=-1;

    df(a,n,d,vf2);                                      ///repetam parcurgerea, pornind din acel varf;

    for(int i=1;i<=n;i++)
        if(d[i]>maxi)
        {
            maxi=d[i];
            vf1=i;                                      ///asftfel, cel mai lung lant din acel arbore va avea celalalt varf in cel mai indepartat nod;
        }
    maxi++;
    fout<<maxi;                     ///afisam cele doua capete si lungimea lantului cerut;
    return 0;
}