Cod sursa(job #2639241)

Utilizator ZahaZaharie Stefan Zaha Data 1 august 2020 08:13:03
Problema Diametrul unui arbore Scor 100
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 = 0, deepestSecond = 0, deepestPos = 0;

void dfs(int node, int level, int &maxLevel) {
	visited[node] = true;
	if (level >= maxLevel) {
		maxLevel = level;
		deepestPos = node;
	}

	for (unsigned i = 0; i < graph[node].size(); ++i)
		if (!visited[graph[node][i]])
			dfs(graph[node][i], level + 1, maxLevel);
	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, deepestSecond);
	dfs(deepestPos, 1, deepest);
	fout << deepest;
	return 0;
}