Cod sursa(job #1259646)

Utilizator sunt_emoSunt emo sunt_emo Data 10 noiembrie 2014 12:14:26
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>

struct Arb
{
  int id;
  std::vector<Arb *> vecs;
  Arb(int id): id(id) {}
};

std::pair<const Arb *, int> parcurg(const Arb *node, int depth, std::vector<bool> &visited)
{
  visited[node->id] = true;
  std::pair<const Arb *, int> ret = std::pair<const Arb *, int>(node, depth);
  
  for (int i = 0; i < (int) node->vecs.size(); i++)
    if (!visited[node->vecs[i]->id])
    {
	  std::pair<const Arb *, int> t = parcurg(node->vecs[i], depth + 1, visited);
	  if (t.second > ret.second)
	    ret = t;
	}
  
  visited[node->id] = false;
  return ret;
}

int main()
{
  std::ifstream in("darb.in");
  std::ofstream out("darb.out");
  
  int n;
  
  in >> n;
  
  std::vector<Arb *> data(n + 1, (Arb *) 0);
  for (int i = 1; i <= n; i++)
    data[i] = new Arb(i);
  for (int i = 0; i < n - 1; i++)
  {
    int x, y;
	in >> x >> y;
	data[x]->vecs.push_back(data[y]);
	data[y]->vecs.push_back(data[x]);
  }
  
  std::vector<bool> visited(n + 1, false);
  std::pair<const Arb *, int> search = parcurg(data[1], 0, visited);
  out << parcurg(search.first, 1, visited).second << '\n';
  
  in.close(), out.close();
}