Cod sursa(job #2604714)

Utilizator buhaidarius@gmail.comBuhai Darius [email protected] Data 23 aprilie 2020 12:33:30
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 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;
    states.push_back(1);
    int counter = 0;
    while(!states.empty()){
        ++counter;
        int cs = states.size();
        for(int i=0;i<cs;i++){
            for(auto ss: arb[states[i]])
                states.emplace_back(ss);
            states.pop_front();
        }
        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;
}