Cod sursa(job #1234408)

Utilizator daniel.amarieiDaniel Amariei daniel.amariei Data 27 septembrie 2014 12:46:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <bitset>
#include <list>
#define SIZE 100001
using namespace std;

int n;
bitset<SIZE> VIZ;
list<int>* ADJ[SIZE];


int last_node_from_bfs(int v)
{
	queue<int>* Q = new queue<int>();
	Q->push(v);
	VIZ[v] = true;
	
	int last_node;
	
	while (!Q->empty())
	{
		last_node = Q->front(); Q->pop();
		
		list<int>* neighbors = ADJ[last_node];
		if (neighbors)
		{
			for (list<int>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
			{
				int u = *it;
				if (!VIZ[u])
				{
					Q->push(u);
					VIZ[u] = true;
				}
			}
		}		
	}
	
	return last_node;
}

int max_length_from_bfs(int v)
{
	queue<pair<int, int> >* Q = new queue<pair<int, int> >();
	Q->push(make_pair(v, 1));
	VIZ[v] = true;
	
	pair<int, int> p;
	while (!Q->empty())
	{
		p = Q->front(); Q->pop();
		int node = p.first;
		int dist = p.second;
	
		list<int>* neighbors = ADJ[node];
		if (neighbors)
		{
			for (list<int>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
			{
				int u = *it;
				if (!VIZ[u])
				{
					Q->push(make_pair(u, dist + 1));
					VIZ[u] = true;
				}
			}
		}		
	}
	
	return p.second;
}

int main()
{
	ifstream ifs("darb.in");
	ofstream ofs("darb.out");
	
	ifs >> n;
	for (int i = 0; i < n; ++i)
	{
		int a, b;
		ifs >> a >> b;
		
		if (ADJ[a] == 00)
			ADJ[a] = new list<int>();

		if (ADJ[b] == 00)
			ADJ[b] = new list<int>();
			
		ADJ[a]->push_back(b);
		ADJ[b]->push_back(a);
	}
	
	int last_node = last_node_from_bfs(1);
	VIZ.reset();
	int path_length = max_length_from_bfs(last_node);
	
	ofs << path_length;
	
	return 0;
}