Cod sursa(job #2674802)

Utilizator Marius05Voina Marius Marius05 Data 20 noiembrie 2020 12:11:38
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

const int NMAX = 100000;

vector<int> G[NMAX + 5];
vector<int> dist;
vector<bool> isNotRoot;
int n, u, v, distmx, i;

void dfs(int u)
{
	int i, mx1 = 1, mx2 = 1;
	if (G[u].empty())
	{
		dist[u] = 1;
		return;
	}
	if (G[u].size() == 1)
	{
		dfs(G[u][0]);
		dist[u] = dist[G[u][0]] + 1;
		return;
	}
	for (i = 0; i < G[u].size(); ++i)
	{
		dfs(G[u][i]);
		if (dist[G[u][i]] > mx2)
			mx2 = dist[G[u][i]];
		if (mx2 > mx1)
			swap(mx1, mx2);
	}
	dist[u] = mx1 + 1;
	if (mx1 + mx2 + 1 > distmx)
		distmx = mx1 + mx2 + 1;
}

int main()
{
	fin >> n;
	dist.assign(n + 5, 0);
	isNotRoot.assign(n + 5, 0);
	for (i = 0; i < n - 1; ++i)
	{
		fin >> u >> v;
		isNotRoot[v] = true;
		G[u].push_back(v);
	}
	for (i = 1; isNotRoot[i]; ++i);
	dfs(i);
	if (dist[i] > distmx)
		distmx = dist[i];
	fout << distmx;
	fin.close();
	fout.close();
	return 0;
}