Cod sursa(job #1264982)

Utilizator j.loves_rockJessica Joanne Patrascu j.loves_rock Data 16 noiembrie 2014 15:49:32
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> g[100001];
int a[100001], dist[100001], sol[100001], q[100001], n, last;
bool ok[100001];
int bfs (int x)
{
    int i, p=1, u=1, nod, Max=0;
    memset(sol,0,sizeof(sol)); memset(q,0,sizeof(q)); memset(ok,0,sizeof(ok));
    sol[x]=1; q[p]=x; ok[x]=true;
    while (p<=u)
    {
        nod=q[p];
        for (i=0; i<g[nod].size(); i++)
        {
            if (ok[g[nod][i]]==false)
            {
                q[++u]=g[nod][i];
                ok[g[nod][i]]=true;
                sol[g[nod][i]]=sol[nod]+1;
                if (sol[nod]+1>Max) Max=sol[nod]+1;
                last=g[nod][i];
            }
        }
        p++;
    }
    return Max;
}
int main()
{
    int m=0, i, j, x, y, Max=0;
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<n; i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs(1);
    bfs(last);
    printf("%d",sol[last]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}