Cod sursa(job #1198522)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 15 iunie 2014 23:55:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#define N 100001
std::vector<std::vector<int> >g(N);
std::vector<bool> viz(N);

std::pair<int,int> dfs(int k) // (lant, belt) 
{
    viz[k]=true;
    int maxlant1=-1, maxlant2=-1, maxbelt=0;
    int lant, belt;

    for(int i=0;i<g[k].size();i++)
    {
        int node = g[k][i];
        if(viz[node]==false)
        {   
            std::pair<int,int> p=dfs(node);    
            lant = p.first;     
            belt = p.second;
            if(lant>maxlant2)
            {
                maxlant1=maxlant2; 
                maxlant2=lant;
            }
            else if(lant>maxlant1)
            {
                maxlant1=lant;  
            }
            if(belt>maxbelt)
            {
                maxbelt=belt;
            }
        }
    }
    std::pair<int, int> ret = std::make_pair(maxlant2+1, std::max(2+maxlant1+maxlant2,maxbelt));
    return ret;
}

int main ()
{
    std::ifstream fin("darb.in");
    std::ofstream fout("darb.out");
    int n,a,b;
    fin>>n;
    g.resize(n+1);
    for(int i=1;i<n;i++)
    {
        fin>>a>>b;  
        g[a].push_back(b);
        g[b].push_back(a);
    }
    std::pair<int,int> ret = dfs(1);
    fout<<std::max(ret.first, ret.second)+1;
    return 0;
}