Cod sursa(job #2954841)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 15 decembrie 2022 16:55:46
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 1e5;
const int inf = 1e9;

vector <int> g[NMAX + 1];
queue <int> q;
int d[NMAX + 1], n;

void bfs(int x){

    d[x] = 0;
    q.push(x);

    while(!q.empty()){

        int nc = q.front();
        q.pop();

        for(auto y : g[nc]){
            if(d[y] > d[nc] + 1){

                d[y] = d[nc] + 1;
                q.push(y);

            }
        }

    }

}

int main(){

    cin >> n;

    for(int i = 0; i < n - 1; i++){

        int x = 0, y = 0;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);

    }

    for(int i = 1; i <= n; i++)
        d[i] = inf;

    bfs(1); // bfs dintr-un nod oarecare

    int nod = 0, dist = 0;

    // caut cel mai indepartat nod de nodul oarecare (1)
    for(int i = 1; i <= n; i++)
        if(d[i] > dist)
            nod = i, dist = d[i];


    for(int i = 1; i <= n; i++)
        d[i] = inf;

    bfs(nod); // bfs din cel mai indepartat nod de nodul oarecare (1)

    int dmax = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] > dmax)
            dmax = d[i];

    cout << dmax + 1; // prin "distanta", ei s-au referit in problema la numarul de noduri ale lantului de lungime maxima (=diametru). Un lant
                    // cu n noduri are n - 1 muchii. Noi am gasit, de fapt, numarul de muchii ale lantului de lungime maxima, deci va trebui
                    // sa adaugam 1 la rezultat (dmax), pentru a afisa numarul de NODURI ale lantului de lungime maxima.
                    // dmax reprezinta, de fapt, numarul de muchii ale lantului (adica n - 1)
                    // dmax = n - 1 / + 1
                    // <=> dmax + 1 = n = distanta ceruta


    return 0;
}