Cod sursa(job #3148446)

Utilizator AlexandruIoan20Moraru Ioan Alexandru AlexandruIoan20 Data 1 septembrie 2023 14:32:55
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 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;

	while(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 + 1); 
		}
	}
}

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, 1); 

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

	cout << dmax << '\n'; 

	return 0; 
}