Cod sursa(job #1690502)

Utilizator mihaelatd96Tudor Mihaela Daniela mihaelatd96 Data 15 aprilie 2016 10:40:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
int n,frunza,lungime=-100;

vector < vector <int> >graph;
vector<int>visited;

void BFS(int vertex)
{
  if((vertex<0)||(vertex>n-1))
  {
    return;
  }
  queue <int> q;
  int element;
  q.push(vertex);
  visited[vertex]=0;

  while(!q.empty())
  {
    element=q.front();
    for(unsigned int i=0;i<graph[element].size(); i++)
    {
      if(visited[graph[element][i]]==-1)
      {
        q.push(graph[element][i]);
        visited[graph[element][i]]=visited[element]+1;
        if (lungime<visited[graph[element][i]])
        lungime=visited[graph[element][i]];

      }
    }
    q.pop();
frunza=element;
  }
}


int main()
{
  int x,y;
  ifstream f("darb.in");
  ofstream g("darb.out");
  f>>n;
  graph.resize(n);
  visited.resize(n,-1);

  for(int i=0; i<n-1; i++)

  {
    f>>x>>y;
    x=x-1;
    y=y-1;
    graph[x].push_back(y);
    graph[y].push_back(x);
  }
BFS(0);
visited.clear();
visited.resize(n,-1);
BFS(frunza);
g<<lungime+1;
  return 0;
}