Cod sursa(job #1991189)

Utilizator netfreeAndrei Muntean netfree 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;
}