Cod sursa(job #2871238)

Utilizator george_buzasGeorge Buzas george_buzas Data 13 martie 2022 19:55:14
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX_NR_NODES 100001
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

vector<int> adjancency_list[MAX_NR_NODES];
queue<int> neighbours;
int distances[MAX_NR_NODES];

void find_max_length_chain(int start_node, int &last_node, int& max_length_chain) {
	memset(distances, 0, sizeof distances);
	neighbours.push(start_node);
	while (!neighbours.empty()) {
		int current_node = neighbours.front();
		int current_nr_neighbours = adjancency_list[current_node].size();
		last_node = current_node;
		neighbours.pop();
		for (int i = 0; i < current_nr_neighbours; ++i) {
			int neighbour = adjancency_list[current_node][i];
			if (!distances[neighbour] && neighbour != start_node) {
				distances[neighbour] = distances[current_node] + 1;
				max_length_chain = max(max_length_chain, distances[neighbour]);
				neighbours.push(neighbour);
			}
		}
	}
}

int main() {
	int nr_nodes;
	fin >> nr_nodes;
	for (int i = 1; i < nr_nodes; ++i) {
		int node_1, node_2;
		fin >> node_1 >> node_2;
		adjancency_list[node_1].push_back(node_2);
		adjancency_list[node_2].push_back(node_1);
	}
	int max_length_chain = 1;
	int last_node = 0; // I only need this node for the first bfs traversal so I know which node is farthest from the start_node so I can use this "last node" as the start node for the second bfs
	find_max_length_chain(1, last_node, max_length_chain);
	find_max_length_chain(last_node, last_node, max_length_chain);
	fout << max_length_chain + 1;
	return 0;
}