Cod sursa(job #2749425)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 6 mai 2021 17:40:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

#define NMAX 100005

int n, dmax, nodmax, lung[NMAX];
vector<int> G[NMAX];
queue<int> q;

void citire() {
    f >> n;
    int nod1, nod2;
    for (int i = 1; i < n; ++i) {
        f >> nod1 >> nod2;
        G[nod1].push_back(nod2);
        G[nod2].push_back(nod1);
    }
}

void element_nou() {
    int nod = q.front();
    q.pop();
    if (lung[nod] > dmax) {
        dmax = lung[nod];
        nodmax = nod;
    }
    for (auto &nod2:G[nod])
        if (!lung[nod2]) {
            lung[nod2] = lung[nod] + 1;
            q.push(nod2);
        }
}

void determinare(int nod) {
    nodmax = nod;
    dmax = 1;
    lung[nod] = 1;
    q.push(nod);
    while (!q.empty())
        element_nou();
}

int main() {
    citire();
    determinare(1);
    for (int i = 1; i <= n; ++i)
        lung[i] = 0;
    determinare(nodmax);
    g << dmax;
    return 0;
}