Cod sursa(job #2883933)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 1 aprilie 2022 23:38:41
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

#define all(a) a.begin(), a.end()
#define range(a, l, r) a.begin() + l, a.begin() + r
#define aall(a, n) a + 1, a + 1 + n
#define arange(a, l, r) a + l, a + r
	
#define maxself(a, b) a = std::max(a, b);
#define minself(a, b) a = std::min(a, b);

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

const int NMAX = 1e5;

int n;
std::vector<int> graph[1 + NMAX];

std::queue<int> q;
int dist[1 + NMAX];

void bfs(int src) {
  dist[src] = 1;
  q.push(src);

  while (!q.empty()) {
    int node = q.front();
    q.pop();

    for (int i : graph[node]) {
      if (dist[i] != 0)
        continue;

      dist[i] = dist[node] + 1;
      q.push(i);
    }
  }
}

int main() {
  inout("darb");

  in >> n;

  for (int i = 1; i <= n; ++i) {
    int a, b;
    in >> a >> b;

    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  bfs(1);

  int first = 1;
  for (int i = 1; i <= n; ++i) {
    if (dist[i] > dist[first])
      first = i;
  }

  memset(dist, 0, sizeof(dist));

  bfs(first);

  int second = 1;
  for (int i = 1; i <= n; ++i) {
    if (dist[i] > dist[second])
      second = i;
  }

  out << dist[second] << '\n';
  
  return 0;
}