Cod sursa(job #1424013)

Utilizator LegionHagiu Stefan Legion Data 23 aprilie 2015 10:44:57
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> drumuri[100001];
int totaldrumuri[100001];
vector<int> frunze;
int lungime[100001];
int tata[100001];
void explora(int loc,int t)
{
    tata[loc]=t;
    int i;
    bool efrunza=true;
    for (i=0;i<drumuri[loc].size();i++)
    {
        if (drumuri[loc][i]!=t)
        {
            efrunza=false;
            explora(drumuri[loc][i],loc);
        }
    }
    if (efrunza==true)
    {
        frunze.push_back(loc);
    }
}
int main()
{
    ifstream in("darb.in");
    ofstream out("darb.out");
    int i,n,x,y,drummaxim=0;
    in>>n;
    for (i=1;i<n;i++)
    {
        in>>x;
        in>>y;
        drumuri[x].push_back(y);
        totaldrumuri[x]++;
        drumuri[y].push_back(x);
        totaldrumuri[y]++;
    }
    explora(1,0);
    for (i=0;i<frunze.size();i++)
    {
        drummaxim=max(drummaxim,lungime[frunze[i]]+1);
        drummaxim=max(drummaxim,lungime[tata[frunze[i]]]+1+lungime[frunze[i]]+1);
        lungime[tata[frunze[i]]]=max(lungime[tata[frunze[i]]],lungime[frunze[i]]+1);
        totaldrumuri[tata[frunze[i]]]--;
        if (totaldrumuri[tata[frunze[i]]]==1)
        {
            frunze.push_back(tata[frunze[i]]);
        }
    }
    out<<drummaxim;
}