Cod sursa(job #1683218)

Utilizator GabiADAndrei Gabriel GabiAD Data 10 aprilie 2016 14:18:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.44 kb
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;

vector <vector <int>> graph;
vector <int> visited;
unsigned int n, m;
int prim, sec, lung = 0;

void BFS(unsigned int vertex)
{
  if(vertex < 0 || vertex > n-1)
    return;

  unsigned int element, i;
  queue <int> q;

  q.push(vertex);
  
  visited[vertex] = 1;

  //cout << vertex + 1 << endl;
  
  while(!q.empty())
    {
      element = q.front();

      for (i = 0; i < graph[element].size(); i++)
	{
	  if(!visited[graph[element][i]])
	    {
	      q.push(graph[element][i]);
	      visited[graph[element][i]] = visited[element] + 1;
	      
	      prim = graph[element][i];
	      
	      //cout << graph[element][i] + 1 << endl;
	    }
	  
	}

      q.pop();

    }
}



/*
void DFS(unsigned int vertex)
{
  
  if(vertex < 0 || vertex > n-1)
    return;

  stack <int> s;
  int element;
  bool found;
  unsigned int i;

  s.push(vertex);

  visited[vertex] = true;

  //cout << vertex + 1 << endl;

  while(!s.empty())
    {
      element = s.top();
      
      found = false;
      
      for (i = 0; i < graph[element].size() && !found; i++)
	{
	  if(!visited[graph[element][i]])
	    {
	      found = true;
	      //cout << graph[element][i] + 1 << endl;
	    }

	}
      
      if(found)
	{
	  i--;
	  s.push(graph[element][i]);

	  visited[graph[element][i]] = true;

	  if(graph[element][i] == prim)
	    {
	      if(s.size() % 2 == 0)
		{
		  int aux = s.size()/2+1;
		  while(s.size() != aux)
		    s.pop();
		  
		  cout << s.top()+1 << " ";
		  s.pop();
		  cout << s.top()+1 << endl;
		}
	      else
		{
		  int aux = s.size()/2+1;
		  while(s.size() != aux)
		    s.pop();

		  cout << s.top()+1 << endl;
		}
		  
	      break;
	    }
	}
      else
	s.pop();
	  
	
    }


}
*/

int main()
{
  ifstream darbi("darb.in");
  ofstream darbo("darb.out");
    
  darbi >> n;
  m = n-1;
  
  graph.resize(n);

  visited.resize(n, false);

  int x, y;
  unsigned int i;

  for (i = 0; i < m; i++)
    {
      darbi >> x >> y;

      x--;
      y--;

      graph[x].push_back(y);
      graph[y].push_back(x);
    }

  BFS(0);

  for(int i = 0; i < visited.size(); i++)
    visited[i] = 0;

  // sec = prim;
  BFS(prim);
  
  int max = 0;
  for(int i = 0; i < visited.size(); i++)
    {
      if(max < visited[i])
	max = visited[i];
    }
  
  darbo << max;


  /*   // centru
  for(int i = 0; i < visited.size(); i++)
    visited[i] = 0;
  DFS(sec);
  */
  
  return 0;
}