Cod sursa(job #3227552)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 1 mai 2024 20:29:04
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;
#define int long long int  
#define N 100005

queue<int> Q;
vector<int> g[N];
int t, n, maxim, maxim_1, best_node, best_node_1, parent[N], used[N], dist[N];

void bfs(int nod, int cnt) {
	memset(dist, 0, sizeof(dist));
	memset(used, 0, sizeof(used));
	Q.push(nod);
	used[nod] = 1;
	dist[nod] = 1;
	while (!Q.empty()) {
		int node = Q.front();
		Q.pop();
		for (auto it : g[node]) {
			if (!used[it]) {
				used[it] = 1;
				dist[it] = dist[node] + 1;
				Q.push(it);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (cnt == 1 && dist[i] > maxim) {
			maxim = dist[i];
			best_node = i;
		}
		else if (cnt == 2 && dist[i] > maxim_1) {
			maxim_1 = dist[i];
			best_node_1 = i;
		}
	}
}

signed main() {
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	bfs(1, 1);
	bfs(best_node, 2);
	cout << maxim_1;
    return 0;
}