Cod sursa(job #3148445)

Utilizator AlexandruIoan20Moraru Ioan Alexandru AlexandruIoan20 Data 1 septembrie 2023 14:31:21
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std; 

ifstream cin("darb.in"); 
ofstream cout("darb.out"); 

int N;
vector <int> g[100002], d; 
bitset <100002> v; 

void citire() {
	d.resize(100002);
	cin >> N;
	int i, j;

	for (int k = 1; k < N; k++) {
		cin >> i >> j;
		g[i].push_back(j);
		g[j].push_back(i);
	}
}; 

void dfs(int nod, int dist) {
	v[nod] = 1; 
	d[nod] = dist; 

	for (auto i : g[nod]) {
		if (!v[i]) {
			dfs(i, ++dist); 
		}
	}
}

int main() {
	citire(); 

	int dmax = 0, k = 0; 
	dfs(1, 0); 

	for (int i = 1; i <= N; i++) {
		if (d[i] > dmax) {
			dmax = d[i];
			k = i;
		}
	}; 

	v.reset(); 
	dmax = 0; 

	dfs(k, 0); 

	for (int i = 1; i <= N; i++) {
		if (d[i] > dmax) {
			dmax = d[i];
		}
	}; 

	cout << dmax << '\n'; 

	return 0; 
}