Cod sursa(job #3121670)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 14 aprilie 2023 18:13:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>
#define NMAX 100005

using namespace std;

int n;
int depth[NMAX];
vector<int> adj[NMAX];

void dfs1(int node, int previous) {

	depth[node] = depth[previous] + 1;
	for (int neigh : adj[node]) {
		if (neigh == previous)
			continue;

		dfs1(neigh, node);
	}
}

int dfs2(int node, int father) {

	int ans = 0;
	for (int neigh : adj[node]) {
		if (neigh == father)
			continue;

		ans = max(ans, 1 + dfs2(neigh, node));
	}

	return ans;
}

void solve()
{
	cin >> n;

	for (int i = 1, a, b; i < n; ++i) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	dfs1(1, 0);

	int best = 1;
	for (int i = 2; i <= n; ++i)
		if (depth[i] > depth[best])
			best = i;

	cout << 1 + dfs2(best, 0) << '\n';
}

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

	// ios_base::sync_with_stdio(0);
	// cin.tie(0);

	int t = 1;
	// cin >> t;
	while(t--)
		solve();

	return 0;
}