Cod sursa(job #2040485)

Utilizator SenibelanMales Sebastian Senibelan Data 15 octombrie 2017 21:05:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");

const int NMAX = 100005;
int N;
vector <int> G[NMAX];
int levels[NMAX];
int far = -1;
int sol;

struct nod{
    int indice, parinte;
};

queue <nod> coada;

void clear(queue <nod> &q){
    queue <nod> replace;
    swap(replace, q);
}

void Read(){
    in >> N;
    for(int i = 1; i <= N - 1; ++i){
        int x, y;
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void BFS(int node){
    nod aux;
    aux.indice = node;
    aux.parinte = 0;
    coada.push(aux);
    while(!coada.empty()){
        nod current_node = coada.front();
        coada.pop();
        for(int i = 0; i < G[current_node.indice].size(); ++i){
            int neighbour = G[current_node.indice][i];
            if(neighbour != current_node.parinte){
                nod auxin; 
                auxin.indice = neighbour; 
                auxin.parinte = current_node.indice;
                coada.push(auxin);
                if(far != -1)
                    levels[neighbour] = levels[current_node.indice] + 1;
            }
        }
        if(coada.empty()){
            if(far == -1)
                far = current_node.indice;
            else
                sol = levels[current_node.indice];
        }
    } 
}


int main(){
    Read();
    BFS(1);
    clear(coada);
    BFS(far);
    out << sol + 1 << "\n";
    return 0;
}