Cod sursa(job #2257455)

Utilizator vulpixbSilvasan Bogdan vulpixb Data 10 octombrie 2018 09:07:21
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>

#define NMAX 100005

using namespace std;

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

vector <int> G[NMAX];

int i, n, x, y, dmax;
bool viz1[NMAX], viz2[NMAX];
int d[NMAX];



void dfs1(int nod)
{
    viz1[nod] = 1;
    int nrvecini = G[nod].size();
    for (int i=0; i<nrvecini; i++)
    {
        int vecin = G[nod][i];
        if (viz1[vecin] == 0)
        {
            d[vecin] = d[nod] + 1;
            dmax = max(dmax, d[vecin]);
            dfs1(vecin);
        }
    }
}

void dfs2(int nod)
{
    viz2[nod] = 1;
    int nrvecini = G[nod].size();
    for (int i=0; i<nrvecini; i++)
    {
        int vecin = G[nod][i];
        if (viz2[vecin] == 0)
        {
            d[vecin] = d[nod] + 1;
            dmax = max(dmax, d[vecin]);
            dfs2(vecin);
        }
    }
}

int main()
{
    fin >> n;

    while (fin >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }

    d[1] = 1;
    dfs1(1);
    i=1;
    while (d[i] != dmax)
        i++;
    d[i] = 1;
    dfs2(i);


    fout << dmax;

    return 0;
}