Cod sursa(job #1468506)

Utilizator Chirita_MateiChirita Matei Chirita_Matei Data 6 august 2015 11:13:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <cstring>

#define Nmax 100005

using namespace std;
ofstream fout("darb.out");
ifstream fin("darb.in");

vector <int> v[Nmax];
int lg[Nmax],ultim,n;

void bfs(int nod)
{
    int c[Nmax]={0},i,j,k=0;
    bool viz[Nmax]={0};

    viz[nod]=1;
    c[1]=nod;
    k=1;
    lg[nod]=1;

    for(i=1;i<=k;i++)
    {
        for(j=0;j<v[c[i]].size();j++)
        {
            if(viz[v[c[i]][j]]==0)
            {
                c[++k]=v[c[i]][j];
                viz[v[c[i]][j]]=1;
                lg[v[c[i]][j]]=lg[c[i]]+1;
                ultim=v[c[i]][j];
            }
        }
    }
}

int main()
{
    int i,x,y;

    fin>>n;

    for(i=1;i<n;i++)
    {
        fin>>x>>y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    bfs(1);
    bfs(ultim);

    fout<<lg[ultim];

    return 0;
}