Cod sursa(job #2604709)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 23 aprilie 2020 12:27:08
Problema Diametrul unui arbore Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

vector<vector<int>> arb;

int max1 = 0, max2 = 0;

void bfs(){
    deque<int> states, new_states;
    states.push_back(1);
    int counter =0;
    while(!states.empty()){
        ++counter;
        new_states.clear();
        for(auto s: states)
            for(auto ss: arb[s])
                new_states.push_back(ss);
        states = new_states;
        if(counter>max1){
            max2 = max1;
            max1 = counter;
        }
    }
}

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

    int n, x, y;
    fin>>n;
    arb.resize(n+1);
    while(--n){
        fin>>x>>y;
        arb[x].push_back(y);
    }
    bfs();
    fout<<max1+max2-1;
    return 0;
}