Cod sursa(job #3289665)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 27 martie 2025 20:56:04
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bitset>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const int nmax = 1e5;

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

int n, u, v, last, diametru;
vector<int> g[nmax + 1];

void bfs(int source) {
  bitset<nmax + 1> visited;
  vector<int> cnt(n + 1, 0);
  queue<int> q;

  visited[source] = true;
  q.push(source);
  cnt[source] = 1;

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

    last = node;
    diametru = cnt[last];

    for (auto nxt : g[node]) {
      if (visited[nxt])
        continue;

      visited[nxt] = true;
      q.push(nxt);
      cnt[nxt] = cnt[node] + 1;
    }
  }
}

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

  bfs(1);
  bfs(last);

  fout << diametru;

  return 0;
}