Cod sursa(job #2012312)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 18 august 2017 14:53:24
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

vector < int > Q[100002];

int n,a,b,v[100002],v2[100002],diametru;

int dfs(int nod,int tata)
{
    vector<int>Q2;
    for (vector<int>:: iterator it=Q[nod].begin();it!=Q[nod].end();++it)
    {
        if (*it!=tata)
        {
            dfs(*it,nod);
            Q2.push_back(v[*it]);
        }
    }
    v[nod]=1;
    int mx2=0;
    if (!Q2.empty())
    {
        for (vector<int>::iterator it=Q2.begin();it!=Q2.end();++it)
            if (*it>mx2)
                mx2=*it;
        v[nod]+=mx2;
    }
    if (Q2.size()>=2)
    {
        int mx1=0;
        for (vector<int>::iterator it=Q2.begin();it!=Q2.end();++it)
            if (*it>mx1&&*it<mx2)
                mx1=*it;
        v2[nod]=1+mx1+mx2;
    }
    diametru=max(diametru,max(v[nod],v2[nod]));
}


int main()
{
    f>>n;
    while (f>>a>>b)
    {
        Q[a].push_back(b);
        Q[b].push_back(a);
    }
    dfs(1,0);
    g<<diametru;
    return 0;
}