Cod sursa(job #3262287)

Utilizator StefanPopescu2Popescu Stefan StefanPopescu2 Data 9 decembrie 2024 17:28:10
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
 #include <fstream>
 #include <vector>
 #include <algorithm>
using namespace std;

 ifstream fin("darb.in");
 ofstream fout("darb.out");
 
 
vector<int> vec[100001];
 


int dist1[100001], dist2[100001];
 

void dfs( int x, int val, int dist[]){
  
  dist[x]=val;
   
  int k = vec[x].size();
  for(int i = 0 ; i< k ; i++)
  {
    if(dist[vec[x][i]]==0)
       dfs(vec[x][i], val+1, dist);
  }
    
}

int main()
{
    int n, m;
    fin >> n ;
     
      
    for(int i=1; i<=n-1; i++)
    {
        int x,y;
       fin>>x>>y; // x----->y
       vec[y].push_back(x); 
       vec[x].push_back(y);  
    }
    
    dfs(1,1, dist1);
    // vf pt care avem maxim
    int vf=1;
    for(int i = 1 ; i <= n; i++)
       if( dist1[vf] < dist1[i] ) vf = i;
    
    dfs(vf, 1, dist2);
    
    int maxim = dist2[1];
    for (int i = 1; i <= n; i++)
      maxim = max(maxim, dist2[i]);
    fout << maxim;
   return 0;
}