Cod sursa(job #2918407)

Utilizator vasi_kosminskiHoroi Vasile vasi_kosminski Data 11 august 2022 14:06:18
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int diameter(const vector<vector<int>>& tree, int node)
{
	if (tree[node].size() == 0)
		return 1;

	int maximum{ 0 };
	int value{ 0 };

	for (int i = 0; i < tree[node].size(); i++)
	{
		value = diameter(tree, tree[node][i]) + 1;
		if (value > maximum)
		{
			maximum = value;
		}
	}

	return value;
}

void add_edges(int no_of_nodes, vector<vector<int>>& tree)
{
	for (int i = 0; i < no_of_nodes; i++)
	{
		int from_node{ 0 };
		int to_node{ 0 };

		fin >> from_node >> to_node;

		tree[from_node].push_back(to_node);
	}
}

int main() {
	int no_of_nodes{ 0 };
	int route_1{ 0 };
	int route_2{ 0 };
	int value{ 0 };

	fin >> no_of_nodes;

	vector<vector<int>> tree(no_of_nodes + 1);
	add_edges(no_of_nodes, tree);

	for (int i = 0; i < tree[1].size(); i++)
	{
		value = diameter(tree, tree[1][i]);

		int aux;

		if (route_2 > route_1)
		{
			aux = route_1;
			route_1 = route_2;
			route_2 = aux;
		}

		if (value > route_1)
		{
			route_1 = value;
		}
		else if (value > route_2)
		{
			route_2 = value;
		}
	}

	fout << route_1 + route_2 + 2;

	return 0;
}