Cod sursa(job #3297931)

Utilizator raresgoidescuGoidescu Rares-Stefan raresgoidescu Data 24 mai 2025 18:37:02
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <vector>
#include <queue>

const int NMAX = 1e5 + 5;

int n;
std::vector<int> adj[NMAX];

int main(void) {
#ifndef LOCAL
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
#endif

	std::cin >> n;

	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		std::cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	std::queue<int> bfs;
	std::vector<bool> vis(n + 1, false);
	std::vector<int> distances(n + 1, 0);

	bfs.push(1);

	while (!bfs.empty()) {
		int curr = bfs.front();
		vis[curr] = true;
		bfs.pop();

		for (auto &neigh : adj[curr]) {
			if (!vis[neigh]) {
				distances[neigh] = distances[curr] + 1;
				bfs.push(neigh);
			}
		}
	}

	int furthest = -1;
	int dist_max = -1;

	for (int i = 1; i <= n; ++i) {
		if (distances[i] > dist_max) {
			dist_max = distances[i];
			furthest = i;
		}
	}

	distances.assign(distances.size(), 0);
	vis.assign(vis.size(), false);

	bfs.push(furthest);

	while (!bfs.empty()) {
		int curr = bfs.front();
		vis[curr] = true;
		bfs.pop();

		for (auto &neigh : adj[curr]) {
			if (!vis[neigh]) {
				distances[neigh] = distances[curr] + 1;
				bfs.push(neigh);
			}
		}
	}

	int dist_max_second = -1;

	for (int i = 1; i <= n; ++i) {
		if (distances[i] > dist_max_second) {
			dist_max_second = distances[i];
		}
	}

	std::cout << dist_max_second + 1 << '\n';

	return 0;
}