Cod sursa(job #1703108)

Utilizator PerugiusGasca Alin-Teodor Perugius Data 16 mai 2016 11:22:29
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
int n,frunza,lungime=-100;
int coada[1000];
int nc;
vector < vector <int> >graph;
vector<int>visited;

void BFS(int vertex)
{ //for(int i=0;i<100;i++)
   // coada[100]=0;
    //nc=0;
  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)
      { //coada[nc]=graph[element][i];
        //nc++;
        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<<"Diametru arbore: "<<lungime+1<<endl;
/*g<<"Raza arbore: "<<(lungime+1)/2<<endl;
g<<"Centru arbore: ";
if((lungime+1)%2==0)
g<<coada[((lungime+1)/2)]<<" "<<coada[((lungime+1)/2)+1];
else g<<visited[(lungime+1)/2];*/

  return 0;
}