Cod sursa(job #1848620)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 16 ianuarie 2017 12:48:51
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int util[100005],n,nrleg,a,b,diametru,nr;
vector <int> v[100005];
vector <int> u;
int main()
{
    in>>n;
    for(int i=1;i<=n;++i)
    {
        in>>a>>b;
        if(util[a]==0)
        {
            u.push_back(a);
            util[a]=1;
        }
        if(util[b]==0)
        {
            u.push_back(b);
            util[b]=1;
        }
        v[a].push_back(b);
        v[b].push_back(a);
    }
    nrleg=n-1;
    while(nrleg>1)
    {
        ++diametru;
        for(int j=0;j<u.size();++j)
        {
            if(v[u[j]].size()==1)
            {
                util[u[j]]=0;
                v[u[j]].erase(v[u[j]].begin());
                u.erase(u.begin()+j);
                --j;
                --nrleg;
            }
        }
        for(int j=0;j<u.size();++j)
        {
            for(int i=0;i<v[u[j]].size();++i)
            {
                if(util[v[u[j]][i]]==0)
                {
                    v[u[j]].erase(v[u[j]].begin()+i);
                    --i;
                }
            }
        }
    }
    out<<diametru+2;
    return 0;
}