Cod sursa(job #2980695)

Utilizator alexia._.fFlorete Alexia Maria alexia._.f Data 16 februarie 2023 19:00:11
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

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

const int NMAX = 100000;
vector <int> muchii[NMAX + 1];
queue <int> coada;
bool vizitat[NMAX + 1];
int contor[NMAX + 1];
int n, x, y, last, diametru;

void breadth_first_search(int node_start)
{
    memset(vizitat, 0, NMAX);
    memset(contor, 0, NMAX);
    coada.push(node_start);
    vizitat[node_start] = true;
    contor[node_start] = 1;

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

        for(auto next_node : muchii[varf])
        {
            if(!vizitat[next_node])
            {
                coada.push(next_node);
                contor[next_node] = contor[varf] + 1;
                vizitat[next_node] = true;

                diametru = contor[next_node];
                last = next_node;
            }
        }
        coada.pop();
    }
}

int main()
{
    in >> n;
    for(int i = 0; i < n - 1; i++)
    {
        in >> x >> y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }

    breadth_first_search(1);
    breadth_first_search(last);

    out << diametru;

    in.close();
    out.close();
    return 0;
}