Cod sursa(job #1546847)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 8 decembrie 2015 19:43:07
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <vector>

using namespace std;

const int MAX = 100002;

vector<int> v[MAX];
int n, m, dist[MAX];

void dfs(int nod);
void normalize(int nod);
int imaxDist();

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int ultnod, a, b;
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }

    dist[1] = 1;
    dfs(1);
    ultnod = imaxDist();
    normalize(ultnod);
    dfs(ultnod);
    printf("%d\n", dist[imaxDist()]);
    return 0;
}
void dfs(int nod)
{
    int fiu;
    vector<int>::iterator it;
    for(it=v[nod].begin(); it!=v[nod].end(); ++it)
    {
        fiu = *it;
        if(!dist[fiu])
        {
            dist[fiu] = dist[nod] + 1;
            dfs(fiu);
        }
    }
}
void normalize(int nod)
{
    for(int i=1; i<=n; i++)
        dist[i] = 0;
    dist[nod] = 1;
}
int imaxDist()
{
    int imax = 1;
    for(int i=2; i<=n; i++)
        if(dist[imax] < dist[i])
            imax = i;
    return imax;
}