Cod sursa(job #1599339)

Utilizator rockzoneCerneanu Valentin rockzone Data 13 februarie 2016 19:35:27
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_N 1000001

using namespace std;

vector<int> nod[MAX_N];
queue<int> coada;
int n,contor[MAX_N],viz[MAX_N],last,diametru;

void bfs(int plecare)
{
    memset(contor,0,MAX_N);
    memset(viz,0,MAX_N);
    coada.push(plecare);
    contor[plecare]=1;
    viz[plecare]=1;
    int i,el;
    while(!coada.empty())
    {
        el=coada.front();
        for(i=0;i<nod[el].size();i++)
        {
            if(viz[nod[el][i]]==0)
            {
                coada.push(nod[el][i]);
                contor[nod[el][i]]=contor[el]+1;
                viz[nod[el][i]]=1;
                diametru=contor[nod[el][i]];
                last=nod[el][i];
            }
        }
        coada.pop();
    }
}

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int n, x, y, i;
    scanf("%d", &n);
    for(i=0;i<n-1;i++)
    {
        scanf("%d %d", &x, &y);
        nod[x].push_back(y);
        nod[y].push_back(x);
    }
    bfs(1);
    bfs(last);
    printf("%d", diametru);
    return 0;
}