Cod sursa(job #2638746)

Utilizator ZahaZaharie Stefan Zaha Data 29 iulie 2020 16:56:22
Problema Diametrul unui arbore Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

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;
	fin >> n;

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

		if (i == 1)
			root = x;

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

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