Cod sursa(job #2604734)

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

using namespace std;

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

int maxcount = -9999;

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;
}

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

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();
    dfs(ln);
    fout<<maxcount+1;
    return 0;
}