Cod sursa(job #2886487)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 7 aprilie 2022 20:06:05
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;

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

const int max_size = 1e5 + 1;

int vizitat[max_size], rez;
vector <int> edges[max_size];
queue <int> coada;

void bfs (int nod)
{
    vizitat[nod] = 1;
    coada.push(nod);
    while (!coada.empty())
    {
        nod = coada.front();
        coada.pop();
        for (auto f : edges[nod])
        {
            if (vizitat[f] == 0 || vizitat[nod] + 1 < vizitat[f])
            {
                vizitat[f] = vizitat[nod] + 1;
                rez = max(rez, vizitat[f]);
                coada.push(f);
            }
        }
    }
}

int main ()
{
    ios_base::sync_with_stdio(false);
    in.tie(0);
    out.tie(0);
    int n;
    in >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        in >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    bfs(1);
    int max1 = 0, indice = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vizitat[i] > max1)
        {
            max1 = vizitat[i];
            indice = i;
        }
        vizitat[i] = 0;
    }
    rez = 1;
    bfs(indice);
    out << rez;
    in.close();
    out.close();
    return 0;
}