Cod sursa(job #1149521)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 21 martie 2014 22:53:11
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<queue>
#define maxn 100005
using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");

vector <int> a[maxn];
queue <int> q;
int i,n,x,y,d[maxn];
int ultim_nod,ultim;

void bfs(int plecare,int &ultim){
     int i,lung,nod;
     
     d[plecare]=1; q.push(nod);
     
     while(q.size())
      {
       nod=q.front();
       if(d[nod]>ultim){
                        ultim=d[nod];
                        ultim_nod=nod;
                       }
       
       lung=a[nod].size();
       for(i=0;i<lung;i++)
         if(!d[a[nod][i]]){
                           d[a[nod][i]]=d[nod]+1;
                           q.push(i);
                          }
       q.pop();
      }
}

int main(){
    fi>>n; 
    for(i=1;i<=n;i++) d[i]=0;
    for(i=1;i<n;i++){
                     fi>>x>>y;
                     a[x].push_back(y);
                     a[y].push_back(x);
                    }
                    
    ultim_nod=1; ultim=1; 
    bfs(1,ultim);
    
    for(i=1;i<=n;i++) d[i]=0;
    bfs(ultim_nod,ultim);
    
    fo<<ultim;
    
    fi.close();
    fo.close();
    return 0;
}