Cod sursa(job #2052568)

Utilizator SederfoMarius Vlad Sederfo Data 30 octombrie 2017 19:27:11
Problema Diametrul unui arbore Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Nmax=100000;
int N, dmax, dist[Nmax];


vector < int > listaAdiacenta[Nmax+5];
queue < int > coada;

void Read()
{
    fin >> N;
    for (int i=1; i<=N-1; i++)
    {
        int x, y;
        fin >> x >> y;
        listaAdiacenta[x].push_back(y);
        listaAdiacenta[y].push_back(x);
    }
    fin.close();
}

void ClearQueue(queue < int > q)
{
    while (!q.empty())
        q.pop();
}

void BFS(int nod)
{
    ClearQueue(coada);
    coada.push(nod);
    for (int i=1; i<=N; i++)
        dist[i]=-1;
    dist[nod]=1;
    while (!coada.empty())
    {
        int nodCurent=coada.front();
        coada.pop();
        for (int i=0; i<(int)listaAdiacenta[nodCurent].size(); i++)
        {
            int vecin=listaAdiacenta[nodCurent][i];
            if (dist[vecin]==-1)
                {
                    dist[vecin]=dist[nodCurent]+1;
                    if (dist[vecin]>dmax)
                        dmax=dist[vecin];
                    coada.push(vecin);
                }
        }
    }
}

void Print()
{
    fout << dmax << "\n";
}

int main()
{
    Read();
    for (int i=1; i<=N; i++)
        BFS(i);
    Print();
    return 0;
}