Cod sursa(job #2784863)

Utilizator Gabriel_DascalescuGabriel Dascalescu Gabriel_Dascalescu Data 17 octombrie 2021 16:02:32
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#define nmax 100005

using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

int dist1[nmax], distpunct[nmax], maxim, n, a, b, nod, maxim2;

vector <int> graf[nmax];

bool viz[nmax];

void dfs1(int a)
{
    viz[a] = 1;
    for(int i=0; i<graf[a].size(); i++)
    {
        if(viz[graf[a][i]]==0)
        {
            dist1[graf[a][i]] = dist1[a]+1;
            dfs1(graf[a][i]);
        }
    }
}


int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs1(1);
    for(int i=1; i<=n; i++)
    {
        if(dist1[i] >maxim )
        {
            maxim = dist1[i];
            nod = i;
        }
        dist1[i]=0;
        viz[i]=0;
    }
    //out<<nod<<"\n";
    dfs1(nod);
    for(int i=1; i<=n; i++)
    {
        if(dist1[i] >maxim2)
            maxim2= dist1[i];
    }
    out<<maxim2+1;
    return 0;
}