Cod sursa(job #1615729)

Utilizator andreitulusAndrei andreitulus Data 26 februarie 2016 19:54:16
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#include <vector>
#define maxn 100003
using namespace std;

vector <int> L[maxn];
int n, c[maxn], v[maxn], d[maxn];

void read()
{
    int i, p1, p2;

    scanf("%d", &n);

    for(i = 1; i < n; i++)
    {
        scanf("%d %d", &p1, &p2);

        L[p1].push_back(p2);
        L[p2].push_back(p1);
    }
}



void BFS(int r)
{
    int p, u, k, i;


    for(i = 1; i <= n; i++)
        d[i] = v[i] = 0;

    p = u = 1;
    v[r] = 1;
    c[u] = r;
    d[r] = 1;


    while(p <= u)
    {
        k = c[p];

        for(i = 0; i < L[k].size(); i++)
            if(v[L[k][i]] == 0)
            {
                v[L[k][i]] = 1;
                u++;
                c[u] = L[k][i];

                d[L[k][i]] = d[k] + 1;

            }

        p++;
    }
}



void solve()
{
    int i, maxx = 0, m;

    BFS(1);

    for(i = 1; i <= n; i++)
        if(d[i] > maxx)
        {
            maxx = d[i];
            m = i;
        }

    BFS(m);

    maxx = 0;

    for(i = 1; i <= n; i++)
        if(d[i] > maxx)
            maxx = d[i];

    printf("%d", maxx);

}




int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    read();

    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}