Cod sursa(job #1234358)

Utilizator daniel.amarieiDaniel Amariei daniel.amariei Data 27 septembrie 2014 11:19:28
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <bitset>
#define SIZE 100001
using namespace std;

int n;
bitset<SIZE> VIZ;
bitset<SIZE> 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();
		
		for (int i = 1; i <= n; ++i)
		{
			if (ADJ[last_node][i] && !VIZ[i])
			{
				Q->push(i);
				VIZ[i] = 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;
	
		for (int i = 1; i <= n; ++i)
		{
			if (ADJ[node][i] && !VIZ[i])
			{
				Q->push(make_pair(i, dist + 1));
				VIZ[i] = 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;
		
		ADJ[a][b] = ADJ[b][a] = true;
	}
	
	int last_node = last_node_from_bfs(1);
	VIZ.reset();
	int path_length = max_length_from_bfs(last_node);
	
	ofs << path_length;
	
	return 0;
}