Cod sursa(job #2289483)

Utilizator anonimulsbanonimul sibian anonimulsb Data 24 noiembrie 2018 17:42:19
Problema Diametrul unui arbore Scor 100
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");
ofstream g("darb.out");
int n;
struct pereche{int frunza, inaltime;};

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(1,diametru,varf);
    cout << varf << ' ' << diametru<<endl;

    g  << diametru+1<<endl;
    return 0;
}