Cod sursa(job #1536090)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 25 noiembrie 2015 18:01:31
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<queue>
#include<vector>
#include<fstream>
using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");

const int MAX_N = 100005;

vector <int> a[MAX_N];
int i,n,x,y,ultim,d_ultim;

void bfs(int nod, int &ultim, int &d_ultim){
     queue <int> q;
     int d[MAX_N];
     
     for(int i=1;i<=n;i++) d[i]=0;
     q.push(nod); d[nod]=1;
     
     while(!q.empty()){
          int x = q.front();     
          q.pop();
          
          if(d[x]>d_ultim){
                           d_ultim = d[x];
                           ultim = x;
                          }
          
          for(unsigned int j=0;j<a[x].size();j++)
            if(!d[a[x][j]]){
                            int y = a[x][j];
                            d[y] = d[x] + 1;
                            q.push(y);
                           }
     }
}

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