Cod sursa(job #2540464)

Utilizator anamaria_panait.10Panait Ana-Maria anamaria_panait.10 Data 7 februarie 2020 10:31:34
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

vector<int> graf[1000001];
queue<int> coada;

int n,contor[1000001],viz[1000001],last,diametru;

void bfs(int plecare){
  
  memset(contor,0,n);
  memset(viz,0,n);

  coada.push(plecare);
  contor[plecare]=1;
  viz[plecare]=1;
  
  int vf;
  while(!coada.empty()){

    vf = coada.front();
    for(int i = 0; i < graf[vf].size();i++){
       if(viz[graf[vf][i]] == 0){
           coada.push(graf[vf][i]);
           contor[graf[vf][i]] = contor[vf] + 1;
           viz[graf[vf][i]] = 1;
           diametru = contor[graf[vf][i]];
           last = graf[vf][i];
      }

    }
    coada.pop();

  }

}

void citire(){

  int a, b;
  in >> n;
  for(int i = 0; i < n - 1; i++){
    in >> a >> b;
    graf[a].push_back(b);
    graf[b].push_back(a);
  }

}

int main()

{

  citire();
  bfs(1);
  bfs(last);
  out << diametru;
  return 0;

}