Cod sursa(job #1698679)

Utilizator Raluca_Mindrutralucam Raluca_Mindrut Data 5 mai 2016 00:27:30
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;
ifstream f("darb.in");
ofstream g("darb.out");
int n,diam;
vector<vector<int> > graph;
vector<int>visited;
int bfs(int vertex)
{
    if(vertex<0 || vertex>n-1) return -1;
    queue <int> q;
    int element,i;
    q.push(vertex);
    visited[vertex]=true;
    while(!q.empty())
    {
        element = q.front();
        for(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;

                }

        }q.pop();
    }
    diam=visited[element];
    return element;

}


int main()
{
  f>>n;
  graph.resize(n);
  visited.resize(n,-1);
  int x,i,y,first,last;
  for(i=0;i<n-1;i++)
  {
      f>>x>>y;
      x--;
      y--;
      graph[x].push_back(y);
      graph[y].push_back(x);

  }
  first=bfs(0);
  visited.clear();

  visited.resize(n,-1);
  last=bfs(first);
  g<<diam;

  return 0;
}