Pagini recente » Cod sursa (job #2363508) | Cod sursa (job #1851733) | Cod sursa (job #1520923) | Cod sursa (job #1878539) | Cod sursa (job #3280692)
// 100 Puncte
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("darb.in");
ofstream fout ("darb.out");
vector <int> g[100005];
int deepest_node = 0, maxi_level = -1;
int diametru = -1;
bool visited1[100005], visited2[100005];
void dfs (int nod, int level) {
visited1[nod] = 1;
if (level>maxi_level) {
deepest_node = nod;
maxi_level = level;
}
for (int vecin : g[nod]) {
if (!visited1[vecin]) {
dfs(vecin, level+1);
}
}
}
void dfs2 (int nod, int level) {
visited2[nod] = 1;
diametru = max (diametru, level);
for (int vecin : g[nod]) {
if (!visited2[vecin]) {
dfs2(vecin, level+1);
}
}
}
int main()
{
fin.tie(0); fin.sync_with_stdio(false);
int n, x, y; fin>>n;
for (int i=1; i<n; i++) {
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
/* Mergem pana la cea mai indepartata frunza, dupa din frunza aia mergem pana la cea mai indepartata
fruznza, iar distanta dintre ele este diametrul arborelui */
dfs(1, 1);
dfs2(deepest_node, 1);
fout<<diametru;
return 0;
}