Cod sursa(job #2195818)

Utilizator radu20000Radu Harabagiu radu20000 Data 17 aprilie 2018 13:43:49
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define NMAX 1000001

using namespace std;

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

vector<int> nod[NMAX];
queue<int> coada;
int n,contor[
NMAX],viz[NMAX],last,diametru;
void citire();
void bfs(int);

 int main(){
    citire();
    bfs(1);
    bfs(last);
    fout<<diametru;
    return 0;
}
void citire(){
    int i,a,b;
    fin>>n;
    for(i=0;i<n-1;i++){
        fin>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
}

void bfs(int start){
    memset(contor,0,NMAX);
    memset(viz,0,NMAX);
    coada.push(start);
    contor[start]=1;
    viz[start]=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();
    }
}