Cod sursa(job #2540580)

Utilizator anamaria_panait.10Panait Ana-Maria anamaria_panait.10 Data 7 februarie 2020 12:39:47
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector <int> lista[100001];
int coada[100005], viz[100005];
int diametru, nod;

void bfs(int x)
{
    int p, u, vf;
    p = u = 1;
    coada[1] = x;
    viz[vf] = 1;
    while(p <= u)
    {
        vf = coada[p];
        for(int i = 0; i < lista[vf].size(); i++){
            if(viz[lista[vf][i]] == 0)
            {
                u++;
                coada[u] = lista[vf][i];
                viz[lista[vf][i]] = viz[vf] + 1;

                if(viz[lista[vf][i]] > diametru)
                {
                    diametru = viz[lista[vf][i]];
                    nod = lista[vf][i];
                }
            }
        p++;
        }
    }
}

int main()

{

    int n, n1,n2;
    in >> n;
    for(int i = 1; i < n; i++)
    {
        in >> n1 >> n2;
        lista[n1].push_back(n2);
        lista[n2].push_back(n1);
    }

    bfs(1);
    for(int i = 1; i <= n; i++)
        viz[i] = 0;

    bfs(nod);
    out << diametru;

    return 0;

}