Cod sursa(job #2708822)

Utilizator andreic06Andrei Calota andreic06 Data 19 februarie 2021 14:48:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
const int N_MAX = 1e5;

vector<int> graf[1 + N_MAX];
int dist[1 + N_MAX];
int visited[1 + N_MAX];

ifstream fin ( "darb.in" );
ofstream fout ( "darb.out" );

void clear_dist_visited () {
    for ( int i = 1; i <= N_MAX; i ++ )
       dist[i] = 0, visited[i] = 0;
}

void bfs ( int root ) {
    dist[root] = 0; visited[root] = 1;
    queue<int> bfs_q;

    bfs_q.push ( root );
    while ( !bfs_q.empty () ) {
       int node = bfs_q.front (); bfs_q.pop ();
       int new_dist = dist[node] + 1;
       for ( auto x : graf[node] ) {
          if ( !visited[x] ) {
            dist[x] = new_dist;
            visited[x] = 1;
            bfs_q.push ( x );
          }
       }
    }
}


int main()
{
   int n; fin >> n;
   for ( int i = 1; i <= n; i ++ ) {
      int u, v; fin >> u >> v;
      graf[u].push_back ( v );
      graf[v].push_back ( u );
   }

   bfs ( 1 );
   int max_node = -1; int max_dist = 0;
   for ( int i = 1; i <= n; i ++ ) {
      if ( dist[i] > max_dist ) {
        max_dist = dist[i];
        max_node = i;
      }
   }

   clear_dist_visited ();


   bfs ( max_node ); max_dist = 0;
   for ( int i = 1; i <= n; i ++ )
      if ( max_dist < dist[i] )
        max_dist = dist[i];
   fout << max_dist + 1;



    return 0;
}