Cod sursa(job #2810098)

Utilizator andreea.ioanaSora Andreea-Ioana andreea.ioana Data 28 noiembrie 2021 14:41:09
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

int nrN;
vector <vector <int>> listaAd;

vector <int> BFS(int start)
{
    vector <int> cost(nrN + 1, -1);
    int S;
    queue <int> coada;
    coada.push(start);
    cost[start] = 0;
    while (!coada.empty())
    {
        S = coada.front();
        for (int i = 0; i < listaAd[S].size(); i++)
        {
            int nod_curent = listaAd[S][i];
            if (cost[nod_curent] == -1)
            {
                cost[nod_curent] = cost[S] + 1;
                coada.push(nod_curent);
            }
        }
        coada.pop();
    }
    return cost;
}

int main()
{
    int st, dr;
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> nrN;
    listaAd = vector <vector <int>> (nrN + 1);
    for (int i = 1; i <= nrN - 1; i++)
    {
        fin >> st >> dr;
        listaAd[st].push_back(dr);
        listaAd[dr].push_back(st);
    }
    int maxim = 0, ultimulElement;
    vector <int> rez = BFS(1);
    for (int i = 1; i < rez.size(); i++)
        if (rez[i] > maxim)
        {
            maxim = rez[i];
            ultimulElement = i;
        }
    rez = BFS(ultimulElement);
    maxim = 0;
    for (int i = 1; i < rez.size(); i++)
        if (rez[i] > maxim)
            maxim = rez[i];
    fout << maxim + 1;
    fin.close();
    fout.close();
    return 0;
}