Cod sursa(job #1235059)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 28 septembrie 2014 18:05:01
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream ka("darb.in");
ofstream ki("darb.out");

const int N_MAX = 100000;
bool nu[N_MAX + 1];
int lant_maximal;
vector< vector<int> >noduri(N_MAX + 1);
int n, x, y;

int parcurgere(int t)
{
    int maxim = 0, lant_maxim = 0;
    for(int i = 0; i < noduri[t].size(); i++)
    {
        int rezultat = parcurgere(noduri[t][i]);
        if(maxim + rezultat + 1 > lant_maxim)
            lant_maxim = maxim + rezultat + 1;
        if(rezultat > maxim)
        {
            maxim = rezultat;
        }
    }
    if(lant_maxim > lant_maximal)
        lant_maximal = lant_maxim;
    return maxim + 1;
}

int main()
{
    ka >> n;
    for(int i = 1; i <= n; i++)
    {
        ka >> x >> y;
        noduri[x].push_back(y);
        nu[y] = true;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!nu[i])
        {
            parcurgere(i);
        }
    }
    ki << lant_maximal;
}