Cod sursa(job #1989943)

Utilizator b10nd3Oana Mancu b10nd3 Data 9 iunie 2017 17:58:34
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<queue>
#include<vector>
using namespace std;


void zero(int level[], int n){
  for(int i=1;i<=n;i++) level[i]=0;
}

int bfs(queue<int> &auxQ, vector<int> tree[],int level[],int checked[]){
   int a;
   vector<int>::iterator it;
   while(!auxQ.empty()){
     a=auxQ.front(); auxQ.pop();
     for(it=tree[a].begin(); it!=tree[a].end(); it++){
       if(checked[*it]==0){
          auxQ.push(*it); 
          level[*it]=level[a]+1;
          checked[*it]=1;
       }
     }
   }
   return a;
}

int main(){
ifstream in("darb.in"); ofstream out("darb.out");
int n; in>>n;
vector<int> tree[n+1];
queue<int> auxQ;
int i,a,b,level[n+1],checked[n+1];
for(i=0;i<n-1;i++){
  in>>a>>b;
  tree[a].push_back(b);
  tree[b].push_back(a);
}

auxQ.push(1); zero(level,n); zero(checked,n); level[1]=1; checked[1]=1;
a=bfs(auxQ,tree,level,checked);
auxQ.push(a); zero(level,n); zero(checked,n); level[a]=1; checked[a]=1;
b=bfs(auxQ,tree,level,checked);
out<<level[b];

in.close(); out.close();
return 0;
}