Cod sursa(job #2638834)

Utilizator euyoTukanul euyo Data 30 iulie 2020 09:42:13
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MaxN = 100002;

vector<int> arb[MaxN];
int d[MaxN];
int viz[MaxN];

void DFS( int node, int depth ) {
  viz[node] = 1;
  d[node] = depth;
  for ( int i = 0; i < arb[node].size(); ++i ) {
	if ( !viz[arb[node][i]] ) {
	  DFS( arb[node][i], depth + 1 );
	}
  }
}

int main() {
  int n, i, x, y, startNode, mx;

  fin >> n;
  for ( i = 1; i < n; ++i ) {
    fin >> x >> y;
    arb[x].push_back( y );
	arb[y].push_back( x );
  }
  DFS( 1, 1 );
  mx = d[1];
  startNode = 1;
  for ( i = 2; i <= n; ++i ) {
	if ( mx < d[i] ) {
	  mx = d[i];
	  startNode = i;
	}
  }
  for ( i = 1; i <= n; ++i ) {
	viz[i] = d[i] = 0;
  }
  DFS( startNode, 1 );
  mx = 0;
  for ( i = 1; i <= n; ++i ) {
	if ( mx < d[i] ) {
	  mx = d[i];
	}
  }
  fout << mx;
  fin.close();
  fout.close();
  return 0;
}