Cod sursa(job #2849017)

Utilizator george_buzasGeorge Buzas george_buzas Data 14 februarie 2022 13:03:29
Problema Diametrul unui arbore Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

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

void bfs_traversal(int start_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();
		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;
	for (int node = 1; node <= nr_nodes; ++node) {
		bfs_traversal(node, max_length_chain);
	}
	fout << max_length_chain + 1;
	return 0;
}