Cod sursa(job #2636291)

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

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

const int nmax = 100100;
int n, last_node, dist[nmax], dist_max;
bool reached[nmax];
vector <int> muchii[nmax];

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

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

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

                last_node = muchii[vecin][i]; //practic frunza
                dist_max = dist[muchii[vecin][i]];
            }
        }

    }
}

void restart()
{
    for (int i = 1; i <= n; i++)
        reached[i] = false;
    for (int i = 1; i <= n; i++)
        dist[i] = 0;
}

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

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

    bfs(1); // ma duc pana la cea mai indepartata frunza
    restart(); // am facut restart intrucat o sa treaca iar prin graf
    bfs(last_node); // plec de la frunza si ma duc pana la alta cea mai indepartata frunza

    cout << dist_max + 1;
}