Cod sursa(job #1094756)

Utilizator fhandreiAndrei Hareza fhandrei Data 29 ianuarie 2014 20:06:02
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
// Include
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

// Definitii
#define pb push_back

// Constante
const int sz = (int)1e5+1;

// Variabile
ifstream in("darb.in");
ofstream out("darb.out");

int nodes;

vector<int> graph[sz];

queue<int> bfsq;
int dist[sz];

// Main
int main()
{
    in >> nodes;
	
	int rFrom, rTo;
	for(int i=1 ; i<nodes ; ++i)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		graph[rTo].pb(rFrom);
	}
	
	bfsq.push(1);
	dist[1] = 1;
	
	int node;
	while(!bfsq.empty())
	{
		node = bfsq.front();
		bfsq.pop();
		
		vector<int>::iterator it, end=graph[node].end();
		for(it=graph[node].begin() ; it!=end ; ++it)
		{
			if(!dist[*it])
			{
				dist[*it] = dist[node] + 1;
				bfsq.push(*it);
			}
		}
	}
	
	memset(dist, 0, sizeof(dist));
	
	dist[node] = 1;
	bfsq.push(node);
	
	while(!bfsq.empty())
	{
		node = bfsq.front();
		bfsq.pop();
		
		vector<int>::iterator it, end=graph[node].end();
		for(it=graph[node].begin() ; it!=end ; ++it)
		{
			if(!dist[*it])
			{
				dist[*it] = dist[node] + 1;
				bfsq.push(*it);
			}
		}
	}
	
	out << dist[node] << '\n';
	
	in.close();
	out.close();
	return 0;
}