Cod sursa(job #1682918)

Utilizator GabiADAndrei Gabriel GabiAD Data 10 aprilie 2016 13:23:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 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, 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;

	    }
	  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;

  BFS(prim);

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