Cod sursa(job #2330006)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 27 ianuarie 2019 19:05:52
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>

#define input "darb.in"
#define output "darb.out"
#define NMAX 100005

using namespace std;

ifstream in(input);
ofstream out(output);

vector < int > muchii[NMAX];
int N, dist[NMAX], uz[NMAX];

void Read_Data()
{
	in >> N;
	for (int i = 1; i < N; i++)
	{
		int x, y;
		in >> x >> y;
		muchii[x].push_back(y);
		muchii[y].push_back(x);
	}
}

void DFS(int nod)
{
	uz[nod] = 1;
	for (unsigned i = 0; i < muchii[nod].size(); i++)
	{
		int new_nod = muchii[nod][i];
		if (!uz[new_nod])
		{
			dist[new_nod] = dist[nod] + 1;
			DFS(new_nod);
		}
	}
}

void Refill()
{
	for (int i = 1; i <= N; i++)
		uz[i] = 0, dist[i] = 0;
}

void Solve()
{
	DFS(1);
	// Find max node
	int node = -1, max_dist = -1;
	for (int i = 1; i <= N; i++)
	if (max_dist < dist[i])
		max_dist = dist[i], node = i;
	Refill();
	DFS(node);
	max_dist = 0;
	for (int i = 1; i <= N; i++)
	if (max_dist < dist[i])
		max_dist = dist[i];
	out << max_dist + 1 << "\n";
}

int main()
{
	Read_Data();
	Solve();
	return 0;
}