Cod sursa(job #3212606)

Utilizator vladdobro07vladdd vladdobro07 Data 11 martie 2024 23:00:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5;

vector<int> g[nmax + 1], lvl(nmax + 1, 0);
vector<bool> viz(nmax + 1, 0);

int n, x, y;

void read() {
	fin >> n;
	for(int i = 1; i <= n - 1; i++) {
		fin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
}

pair<int, int> dfs(int node) {
	if(lvl[node] == 0)
		lvl[node] = 1;
	viz[node] = 1;
	pair<int, int> downest = {node, lvl[node]};
	for(int fiul : g[node]) {
		if(viz[fiul] == 0) {
			lvl[fiul] = lvl[node] + 1;
			pair<int, int> dfiul = dfs(fiul);
			if(dfiul.second > downest.second)
				downest = dfiul;
		}
	}
	return downest;
}

int solve() {
	int furnode = dfs(1).first;
	viz = vector<bool>(nmax + 1, 0);
	lvl = vector<int>(nmax + 1, 0);
	return dfs(furnode).second;
}

int main() {
	read();
	fout << solve() << "\n";
	return 0;
}