Cod sursa(job #1870718)

Utilizator ReeeBontea Mihai Reee Data 6 februarie 2017 20:56:22
Problema Diametrul unui arbore Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <queue>
#define NMAX 100001

using namespace std;

int vt[NMAX], N; // VECTORUL DE TATI SI NUMARUL DE NODURI
bool viz[NMAX]; // VECTORUL DE VIZITATI

queue < pair < int , int > > coada;

int diametru, aux;

// int a[NMAX][NMAX];

void Citire()
{
    ifstream fin("darb.in");
    int x, y;
    fin >> N;
    for (int i = 1;i < N;i++)
        {
            fin >> x >> y;
            vt[y] = x;
        }
    fin.close();
}

void Parcurgere(int start)
{
    viz[start] = true; // VIZITAM POZITIA DE START
    coada.push(make_pair(start, 1)); // BAGAM IN COADA POZITIA DE START
    while (!coada.empty())
    {
        int nod = coada.front().first;
        int pasi = coada.front().second;
        if (pasi > diametru)
        {
            diametru = pasi;
            aux = nod;
        }
        coada.pop();
        if (vt[nod] != 0)
        {
            if (!viz[vt[nod]])
            {
                coada.push(make_pair(vt[nod],pasi + 1));
                viz[vt[nod]] = true;
            }
        }
        for (int i = 1;i <= N;i++)
        {
            if ((vt[i] == nod) && (!viz[i]))
            {
                coada.push(make_pair(i, pasi + 1));
                viz[i] = true;
            }
        }
    }
}

int main()
{
    ofstream fout("darb.out");
    Citire();
    Parcurgere(1);

    for (int i = 1;i <= N;i++)
        viz[i] = false;
    Parcurgere(aux);
    fout << diametru;


    return 0;
}