Cod sursa(job #1691346)

Utilizator pulseOvidiu Giorgi pulse Data 18 aprilie 2016 01:25:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n, max_len, furthest;
vector<vector<int> > arb;
vector<bool> used;

void dfs(int node, int len)
{
  if (len > max_len) {
    max_len = len;
    furthest = node;
  }

  used[node] = true;

   for (vector<int>::iterator it = arb[node].begin(); it != arb[node].end(); ++it) {
    if (!used[*it]) {
      dfs(*it, len + 1);
    }
  } 
}

int main()
{
  fin >> n;
  arb.resize(n);
  used.resize(n, false);
  for (int i = 0, x, y; i < n - 1; ++i) {
    fin >> x >> y;
    x--;
    y--;
    arb[x].push_back(y);
    arb[y].push_back(x);
  }

  dfs(0, 1);
  used.clear();
  used.resize(n, false);
  dfs(furthest, 1);

  fout << max_len;

  return 0;
}