Cod sursa(job #2122684)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 5 februarie 2018 13:28:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

const int NMAX = 100005;

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

vector<int> g[NMAX];
int n, d[NMAX], dmax, node;
bitset<NMAX> v;

void read() {
  in >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    in >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
}

void dfs(int x, int parent) {
  v[x] = 1;
  d[x] = d[parent] + 1;

  for (int y : g[x]) {
    if (!v[y]) {
      dfs(y, x);
      if (d[y] > dmax) {
        dmax = d[y];
        node = y;
      }
    }
  }
}

int main() {

  read();

  dfs(1, 0);
  v.reset();
  fill(d, d + NMAX, 0);
  dmax = 0;
  dfs(node, 0);

  out << dmax;

  return 0;
}