Cod sursa(job #2604733)

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

using namespace std;

vector<int> parents;
vector<vector<int>> childs;
vector<bool> viz;

int bfs(){
    deque<int> states;
    states.push_back(1);
    int ln = -1;
    while(!states.empty()){
        int cs = states.size();
        for(int i=0;i<cs;i++){
            for(auto ss: childs[states.front()])
                states.emplace_back(ss);
            ln = states.front();
            states.pop_front();
        }
    }
    return ln;
}

int dfs(int cn,int count = 0){
    viz[cn] = true;
    int maxcount = count;
    for(auto c: childs[cn])
        if(!viz[c])
            maxcount = max(dfs(c, count+1), maxcount);
    if(!viz[parents[cn]])
        maxcount = max(dfs(parents[cn], count+1), maxcount);
    return maxcount;
}

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

    int n, x, y;
    fin>>n;
    childs.resize(n+1);
    parents.resize(n+1);
    viz.resize(n+1, 0);
    while(--n){
        fin>>x>>y;
        childs[x].push_back(y);
        parents[y] = x;
    }
    int ln = bfs();
    //cout<<ln;
    fout<<dfs(ln)+1;
    //fout<<dfs(ln);
    return 0;
}