Cod sursa(job #1610375)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 23 februarie 2016 14:39:20
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> G[100005];
int n,viz[100005];
void bfs(int cnt,int u)
{
    int v;
    viz[u]=cnt;
    for(int i=0; i < (int)G[u].size(); i++)
    {
        v=G[u][i];
        if(!viz[v])
            bfs(cnt+1,v);
    }
}

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

    int u,v;

    scanf("%d", &n);
    for(int i=1; i<=n-1; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    bfs(1,1);
    int maxx=0,d=1;
    for(int i=1; i<=n; i++)
    {
        if(maxx < viz[i]) maxx=viz[i],d=i;
        viz[i]=0;
    }
    bfs(1,d);
    maxx=0;
    for(int i=1; i<=n; i++)
            if(maxx < viz[i]) maxx=viz[i];

    printf("%d", maxx);

    return 0;
}