Cod sursa(job #1107819)

Utilizator oancea_horatiuOancea Horatiu oancea_horatiu Data 14 februarie 2014 12:58:25
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

vector <pair<int,int> > g[100005];
int n;

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

pair<int,int> bfs(int v)
{
  int check[100005]={0};
  queue <int> q;
  q.push(v);
  int ultV;
  while (!q.empty())
  {
    int e=q.front();
    q.pop();
    vector <pair<int,int> >::iterator it;
    for (it=g[e].begin(); it!=g[e].end(); it++)
    {
      if ((check[(*it).second]==0)&&((*it).second!=v))
      {
        q.push((*it).second);
        check[(*it).second]=check[(*it).first]+1;
      }
    }
    ultV=e;
  }
  return make_pair(check[ultV]+1,ultV);
}


int getDArb()
{
  return bfs(bfs(1).second).first;
}

void write()
{
  ofstream o("darb.out");
  o<<getDArb();
}

int main()
{
  read();
  write();
}