Cod sursa(job #2012319)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 18 august 2017 15:04:10
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 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,mx1=0;
    for (vector<int>::iterator it=Q2.begin(); it!=Q2.end(); ++it)
        if (*it>mx2)
        {
            swap(mx2,mx1);
            mx2=*it;
        }
        else if (*it>mx1)
            mx1=*it;

if (!Q2.empty())
{
    Q2.back()=mx2;
    v[nod]+=Q2.back();
}
if (Q2.size()>=2)
{
    Q2[Q2.size()-2]=mx1;
    v2[nod]=1+Q2.back()+Q2[Q2.size()-2];
}
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;
}