Cod sursa(job #1267620)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 20 noiembrie 2014 02:02:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<vector>
using namespace std;
#define nmax 100000

vector<int> v[nmax + 1];
bool viz[nmax + 1];

int solve(int root, int& down)
{
	if(v[root].size() == 0)
	{
		down = 1;
		return 1;
	}
	
	int max1 = 0, max2 = 0;
	int sol = 0;
	
	for(size_t i = 0;i < v[root].size();++i)
	{
		int tdown = 0;
		int tsol = solve(v[root][i], tdown);
		
		if(tsol > sol)
		{
			sol = tsol;
		}
		
		if(tdown > max1)
		{
			max2 = max1;
			max1 = tdown;
		}
		else if(tdown > max2)
		{
			max2 = tdown;
		}
	}
	
	sol = max(sol, 1 + max1 + max2);
	down = 1 + max1;
	
	return sol;
}
	
int main()
{
	ifstream in("darb.in");
	ofstream out("darb.out");
	
	int n;
	in >> n;
	
	for(int i = 0;i < n - 1;++i)
	{
		int a, b;
		
		in >> a >> b;
		
		--a, --b;
		v[a].push_back(b);
		viz[b] = true;
	}
	
	int down = 0;
	int root = 0;
	
	for(int i = 0;i < n;++i)
	{
		if(viz[i] == false)
		{
			root = i;
			break;
		}
	}
	
	int sol = solve(root, down);
	out<<sol<<"\n";
	in.close();
	out.close();
}