Cod sursa(job #1764260)

Utilizator Grama911Grama Andrei Grama911 Data 25 septembrie 2016 12:40:29
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

vector <int> lv[100];
vector <int> dr[100];
vector <int>::iterator ii;


int main()
{
	int n, x, y;
	f >> n;
	for (int i = 1; i < n; i++)
	{
		f >> x >> y;
		lv[x].push_back(y);
	}
	int l = 1;
	while (!lv[1].empty())
	{
		int i = 1;
		int p;
		dr[l].push_back(1);
		while (!lv[i].empty())
		{
			dr[l].push_back(lv[i].back());
			p = i;
			i = lv[i].back();
		}
		lv[p].pop_back();
		if (lv[p].empty())
			lv[1].pop_back();
		l++;
	}
	/*int i = 1;
	while(!dr[i].empty())
	{
		for (ii = dr[i].begin(); ii != dr[i].end(); ++ii)
			cout << *ii << " ";
		cout << "\n";
		i++;
	}*/
	int max1 = 0, max2 = 0;
	int i = 1;
	while (!dr[i].empty())
	{
		if (dr[i].size() > max1)
			max1 = dr[i].size();
		if (dr[i].size() > max2 && dr[i].size() < max1)
			max2 = dr[i].size();
		i++;
	}

	g <<max1+max2-1;
	return 0;
}