Cod sursa(job #1191525)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 27 mai 2014 22:09:11
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
vector<int> v[100009];
queue<int> coada;
int cost[100009],viz[100009],last,diametru,n;

void bfs(int start)
{

    int i,k;
    for(i = 1 ; i <= n ; i++)
        viz[i] = cost[i] = 0;

    coada.push(start);
    viz[start] = 1;
    cost[start] = 1;
    while(!coada.empty())
    {

        for(i = 0 ; i < v[coada.front()].size() ; i++){
            k = v[coada.front()][i];
            if(!viz[k]){
                cost[k] = cost[coada.front()] + 1;
                viz[k] = 1;
                coada.push(k);
                last = k;
                diametru = cost[k];
            }
        }
        coada.pop();
    }
}

int main()
{

    int x,y,i;
    in>>n;
    for(i = 1 ; i < n ; i++){

        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs(1);
    bfs(last);
    out<<diametru;
    return 0;
}