Cod sursa(job #2651328)

Utilizator Snake2003lalallalal Snake2003 Data 22 septembrie 2020 11:40:47
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define Nmax 100005

using namespace std;

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

vector < int > Numbers[Nmax];
queue < int > Coada;

int Distanta[Nmax];

void BFS(int Nod_Start)
{
    int Nod, Vecin;

    Coada.push(Nod_Start);
    Distanta[Nod_Start] = 1;
    while( !Coada.empty() )
    {
        Nod = Coada.front();
        Coada.pop();
        for(unsigned int i = 0; i < Numbers[Nod].size(); i ++)
        {
            Vecin = Numbers[Nod][i];
            if( Distanta[Vecin] == 0 )
            {
                Distanta[Vecin] = Distanta[Nod] + 1;
                Coada.push(Vecin);
            }
        }
    }

}

int main()
{
    int numar, maxx = -1;
    int maxx2 = -1;
    int vf;
    fin >> vf;
    int x, y;
    while( fin >> x >> y)
    {
        Numbers[x].push_back(y);
        Numbers[y].push_back(x);
    }
    BFS(1);
    for(int i = 1; i <= vf; i ++)
        if(Distanta[i] > maxx)
        {
            maxx = Distanta[i]; // distanta maxima
            numar = i; // nod de distanta maxima
        }
    memset(Distanta, 0, sizeof(Distanta));
    while( !Coada.empty() )
        Coada.pop();
    BFS(numar);
    for(int i = 1; i <= vf; i ++)
        if(Distanta[i] > maxx2)
            maxx2 = Distanta[i];
    fout << maxx2;
    return 0;
}