Cod sursa(job #3231466)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 26 mai 2024 18:08:15
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>

const int32_t MAX_N = 100000;

struct Result {
	int32_t maxDist;
	int32_t maxNode;
};

std::vector<int32_t> adj[MAX_N];

Result DFS(int32_t node, int32_t prev) {
	Result res = { 1, node };
	for(int32_t next : adj[node]) {
		if(next == prev)
			continue;
		Result nextRes = DFS(next, node);
		if(nextRes.maxDist + 1 > res.maxDist) {
			res.maxDist = nextRes.maxDist + 1;
			res.maxNode = nextRes.maxNode;
		}
	}

	return res;
}

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

	int32_t n;
	fin >> n;
	for(int32_t i = 0; i != n - 1; ++i) {
		int32_t x, y;
		fin >> x >> y;
		--x; --y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	Result res1 = DFS(0, -1);
	Result res2 = DFS(res1.maxNode, -1);

	fout << res2.maxDist;

	fin.close();
	fout.close();

	return 0;
}