Cod sursa(job #2855657)

Utilizator tiut_cristianTiut Cristian tiut_cristian Data 22 februarie 2022 18:46:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

int n, s;

struct node
{
    int nrVecini;
    vector<int> vecini;
    int nrArce;
}v[100001];

void citire()
{
    fin >> n;
    for(int i = 1; i < n; i++)
    {
        int a, b;
        fin >> a >> b;
        v[a].vecini.push_back(b);
        v[b].vecini.push_back(a);
    }
}

void initializare()
{
    for(int i = 1; i <= n; i++)
    {
        v[i].nrArce = -1;
        v[i].nrVecini = v[i].vecini.size();
    }
}

void bfs(int s)
{
    queue<int> coada;
    v[s].nrArce = 0;
    coada.push(s);
    while(!coada.empty())
    {
        int top = coada.front();
        coada.pop();
        for(int i = 0; i < v[top].nrVecini; i++)
            if( v[ v[top].vecini[i] ].nrArce == -1 )
            {
                coada.push(v[top].vecini[i]);
                v[ v[top].vecini[i] ].nrArce = v[top].nrArce + 1;
            }
    }
}

int det_imax(node v[])
{
    int iMax = 1;
    for(int i = 2; i <= n; i++)
        if( v[i].nrArce > v[iMax].nrArce )
            iMax = i;
    return iMax;
}

int det_nrmax(node v[])
{
    int nrMax = v[1].nrArce;
    for(int i = 2; i <= n; i++)
        if( v[i].nrArce > nrMax )
            nrMax = v[i].nrArce;
    return nrMax;
}

int main()
{
    citire();

    initializare();
    bfs(1);
    s = det_imax(v);

    initializare();
    bfs(s);
    fout << det_nrmax(v)+1;

    return 0;
}