Cod sursa(job #2636228)

Utilizator richardionelRichard Ionel richardionel Data 17 iulie 2020 12:35:17
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

const int nmax = 100100;
vector <int> muchii[nmax];
bool reached[nmax];
int n, maxx1 ,maxx2, pos;
int dist[nmax];

void add_edge (int a, int b)
{
    muchii[a].push_back(b);
    muchii[b].push_back(a);
}

void bfs(int nod_start)
{
    queue <int> coada;
    coada.push(nod_start);
    reached[nod_start] = true;

    while(!coada.empty())
    {
        int vecin = coada.front();
        coada.pop();

        for (unsigned int i = 0; i < muchii[vecin].size(); i++)
        {
            if(!reached[muchii[vecin][i]])
            {
                coada.push(muchii[vecin][i]);
                dist[muchii[vecin][i]] = dist[vecin] + 1;
                reached[muchii[vecin][i]] = true;
            }
        }
    }
}

int main()
{
    cin >> n;
    int m = n - 1;
    while(m--)
    {
        int nod1, nod2;
        cin >> nod1 >> nod2;
        add_edge(nod1,nod2);
    }

    bfs(1);

    for (int i = 1; i <= n; i++)
    {
        if(maxx1 < dist[i])
        {
            maxx1 = dist[i];
            pos = i;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if(maxx2 < dist[i] && i != pos)
        {
            maxx2 = dist[i];
        }
    }
    cout << maxx1 + maxx2 + 1;
}