Cod sursa(job #2543276)

Utilizator KPP17Popescu Paul KPP17 Data 10 februarie 2020 23:28:08
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
using namespace std;



#define fisier "darb"

#ifdef fisier
    #include <fstream>
    ifstream in(fisier ".in");
    ofstream out(fisier ".out");
#else
    #include <iostream>
    #define in cin
    #define out cout
#endif



const int MAX_N = 100000;

#include <vector>
vector<int> adiacente_cu[MAX_N];

struct ElemCoada {int nod, dist;} coada[MAX_N];

bool explorat[MAX_N];



ElemCoada bfs(int nod_sursa) {

    for (int nod = 0; nod < MAX_N; nod++) explorat[nod] = false;

    explorat[nod_sursa] = true;

    ElemCoada max_dist_elem = *coada = {nod_sursa, 0};

    for (int baza = 0, varf = 1; baza < varf; baza++) {

        //out << "vecini["<<coada[baza].nod<<"] = ";

        for (
            vector<int>::iterator vecin = adiacente_cu[coada[baza].nod].begin();
            vecin != adiacente_cu[coada[baza].nod].end();
            vecin++
        ) {

            if (explorat[*vecin]) {

                continue;

            }

            //out << *vecin << ' ';

            explorat[*vecin] = true;

            coada[varf] = {*vecin, coada[baza].dist + 1};

            if (max_dist_elem.dist < coada[baza].dist + 1) {

                max_dist_elem = coada[varf];

            }

            varf++;

        }

        //out << '\n';

        /*out << "coada = ";
        for (int i = 0; i < varf; i++) {

            out << coada[i].nod << ' ';

        }out << '\n';*/

    }

    return max_dist_elem;

}



int main() {

    ElemCoada primul, al_doilea;

    int n, x, y;

    in >> n;

    while (--n) {

        in >> x >> y;
        x--, y--;

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

    }

    out << bfs(bfs(0).nod).dist + 1;

}









//