Cod sursa(job #2291087)

Utilizator anonimulsbanonimul sibian anonimulsb Data 27 noiembrie 2018 15:33:20
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

bool *viz;
vector <int> *LA;
//int *T;
ifstream f("darb.in");
int n;
//struct pereche{int frunza, inaltime;};
ofstream g("darb.out");
int df(int nod, int &lmax, int &varf)
{
    int max1=-1,max2=-1;
    viz[nod] = true;
    for (int i=0;i<LA[nod].size();i++)
    {
        int x = LA[nod][i];
        if (viz[x]==false)
        {
  //          T[x] = nod;
            viz[x] = true;
            int lungx = df(x,lmax,varf);
            if (lungx > max1) {max2 = max1; max1 = lungx;}
            else
               if (lungx > max2) max2 = lungx;
        }
    }
    if (max1+max2+2 > lmax)
        {
            lmax = max1+max2+2;
            varf = nod;
        }
    return max1+1;
}

int main()
{
    int diametru=-1,varf;
    f >> n;
    viz = new bool[n+2];
    LA = new vector<int>[n+2];
    //T = new int[n+2];
    for (int i=1;i<=n-1;i++)
    {
        int x,y;
        f >> x >> y;
        LA[x].push_back(y);
        LA[y].push_back(x);
    }
    df(20,diametru,varf);
    g<<diametru;
    //cout << varf << ' ' << diametru<<endl;
    return 0;
}