Cod sursa(job #2204348)

Utilizator Andrei243Nitu Mandel Andrei Andrei243 Data 15 mai 2018 16:03:26
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

int main()
{
   ifstream in("darb.in");
   ofstream out("darb.out");

   int nr_noduri;
   in>>nr_noduri;
   vector<bool>folosite;
   vector<vector<int> > lista_adiacenta;
   vector<int> distanta;
   for(int i=0;i<=nr_noduri;i++){
   distanta.push_back(0);
   vector<int> aux;
   lista_adiacenta.push_back(aux);
   folosite.push_back(false);
   }

   for(int i=0;i<nr_noduri;i++){
   int a1,a2;
   in>>a1>>a2;
   lista_adiacenta[a1].push_back(a2);
   lista_adiacenta[a2].push_back(a1);

   }

   int nod_folosit=1;

   queue<int> noduri;

   noduri.push(nod_folosit);

   folosite[nod_folosit]=true;

   int nod_viitor=nod_folosit;

   distanta[nod_folosit]=0;

   int dis_max=0;


   while(!noduri.empty()){


   int nod_act=noduri.front();
   noduri.pop();

   if(distanta[nod_act]>dis_max){
   nod_viitor=nod_act;

   dis_max=distanta[nod_act];}

   for(int i=0;i<lista_adiacenta[nod_act].size();i++){
   if(!folosite[lista_adiacenta[nod_act][i]]){

   folosite[lista_adiacenta[nod_act][i]]=true;

   noduri.push(lista_adiacenta[nod_act][i]);

   distanta[lista_adiacenta[nod_act][i]]=distanta[nod_act]+1;


   }


   }



   }
nod_folosit=nod_viitor;

for(int i=0;i<folosite.size();i++)folosite[i]=false;
for(int i=0;i<distanta.size();i++)distanta[i]=0;
dis_max=0;
noduri.push(nod_folosit);
  while(!noduri.empty()){


   int nod_act=noduri.front();
   noduri.pop();

   if(distanta[nod_act]>dis_max){
   dis_max=distanta[nod_act];}

   for(int i=0;i<lista_adiacenta[nod_act].size();i++){
   if(!folosite[lista_adiacenta[nod_act][i]]){

   folosite[lista_adiacenta[nod_act][i]]=true;

   noduri.push(lista_adiacenta[nod_act][i]);

   distanta[lista_adiacenta[nod_act][i]]=distanta[nod_act]+1;


   }


   }



   }

out<<dis_max+1;
    return 0;
}