Cod sursa(job #1870766)

Utilizator ReeeBontea Mihai Reee Data 6 februarie 2017 21:28:51
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <queue>
#define NMAX 100001

using namespace std;

int vt[NMAX], N; // VECTORUL DE TATI SI NUMARUL DE NODURI
int vf[NMAX]; // VECTOR DE FRECVENTA :(
bool viz[NMAX]; // VECTORUL DE VIZITATI

queue < pair < int , int > > coada;

int diametru, aux;

void Citire()
{
    ifstream fin("darb.in");
    int x, y;
    fin >> N;
    for (int i = 1;i < N;++i)
        {
            fin >> x >> y;
            vt[y] = x;
            ++vf[y];
        }
    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)
        {
            int k = 0;
            if (vt[i] == nod)
            {
                if (!viz[i])
                {
                    coada.push(make_pair(i, pasi + 1));
                    viz[i] = true;
                    ++k;
                }
            }
            if (k > vf[nod])
                break;
        }
    }
}

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;
}