Cod sursa(job #1085462)

Utilizator fmins123FMI No Stress fmins123 Data 17 ianuarie 2014 00:14:52
Problema Diametrul unui arbore Scor Ascuns
Compilator cpp Status done
Runda Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_N 1000001

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

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

void bfs(int plecare){
    memset(contor,0,sizeof(contor));
    memset(viz,0,sizeof(contor));
    diametruCurent=0;
    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;

                if(diametruCurent<contor[nod[el][i]])
                    diametruCurent=contor[nod[el][i]];
            }
        }
        coada.pop();
    }
}

void citire(){
    int i,a,b;
    f>>n;
    for(i=0;i<n-1;i++){
        f>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
}

int main()
{
    citire();

    for(int i=1;i<=n;i++){
        bfs(i);
        if(diametruCurent>best)
            best=diametruCurent;
    }
    g<<best;

    return 0;
}