Mai intai trebuie sa te autentifici.
Cod sursa(job #1991189)
Utilizator | Data | 15 iunie 2017 16:01:05 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("darb.in");
ofstream fout("darb.out");
const int MAX_N = 100000 + 5;
vector<int> vec[MAX_N];
bitset<MAX_N> viz1, viz2;
int n;
pair<int,int> dfs(int nod, bitset<MAX_N> viz){
viz[nod] = true;
pair<int, int> solve = {0,0};
int fiu = 0;
for(auto i : vec[nod]){
if(!viz[i]){
++fiu;
pair<int, int> ans_temp = dfs(i, viz);
if(ans_temp.second > solve.second)
solve = ans_temp;
}
}
solve.second ++;
if(fiu == 0)
solve = {nod, 1};
return solve;
}
int main()
{
fin >> n;
int nod_start;
for(int i = 1, a, b; i<=n-1; ++i){
fin >> a >> b;
nod_start = b;
vec[a].push_back(b);
vec[b].push_back(a);
}
pair<int, int> ans = dfs(nod_start, viz1);
pair<int, int> ans2 = dfs(ans.first, viz2);
fout << ans2.second;
return 0;
}