Cod sursa(job #2638742)

Utilizator ZahaZaharie Stefan Zaha Data 29 iulie 2020 16:50:03
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

vector<int> graph[100005];
bitset<100005> visited;
int deepest = -1, deepestSecond = -1;

void dfs(int node, int level) {
	visited[node] = true;
	if (level >= deepest) {
		deepestSecond = deepest;
		deepest = level;
	} else if (level > deepestSecond)
		deepestSecond = level;

	for (unsigned i = 0; i < graph[node].size(); ++i)
		if (!visited[graph[node][i]])
			dfs(graph[node][i], level + 1);

	visited[node] = false;
}

int main() {
	int n;
	cin >> n;

	int root;
	for (int i = 1; i < n; ++i) {
		int x, y;
		cin >> x >> y;

		if (i == 1)
			root = x;

		graph[x].emplace_back(y);
		graph[y].emplace_back(x);
	}

	dfs(root, 0);
	cout << deepest + deepestSecond + 1;
	return 0;
}