Cod sursa(job #1386604)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 13 martie 2015 09:00:53
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector<int> G[100001];
int n, m, i, j, U[100001], max1[100001], max2[100001], maxi, lmax;

void DF(int nod)
{   int k;
    U[nod]=1;
    for (k=0; k<G[nod].size(); ++k)
        if (!U[G[nod][k]])
        {   DF(G[nod][k]);
            if (max1[G[nod][k]]+1>max1[nod])
            {   max2[nod]=max1[nod];
                max1[nod]=max1[G[nod][k]]+1;
            }
            else
                if (max1[G[nod][k]]+1>max2[nod])
                    max2[nod]=max1[G[nod][k]]+1;
        }
    lmax=max1[nod]+max2[nod]+1;
    if (lmax>maxi)
        maxi=lmax;
}

int main()
{   f>>n;
    m=n-1;
    for (; m; --m)
    {   f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    DF(1);
    g<<maxi<<'\n';
    return 0;
}