Cod sursa(job #1095022)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 30 ianuarie 2014 11:19:03
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

int n,d[100010],maxi,start;
vector <int> v[100010];
queue <int> Queue;

void citire() {

    ifstream in("darb.in");
    int i,x,y;
    in>>n;
    for(i=1;i<=n-1;i++) {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    in.close();

}

void solve() {

    int i,j,nod,vecin;
    for(i=2;i<=n;i++)
        d[i]=99999999;
    d[1]=0;
    Queue.push(1);
    while(!Queue.empty()){
        nod=Queue.front();
        Queue.pop();
        for(j=0;j<v[nod].size();j++) {
            vecin=v[nod][j];
            if(d[vecin]>d[nod]+1){
                d[vecin]=d[nod]+1;
                Queue.push(vecin);
            }
            if(d[vecin]>maxi){
                maxi=d[vecin];
                start=vecin;
            }

        }
    }

    for(i=1;i<=n;i++)
        d[i]=99999999;
    d[start]=0;
    Queue.push(start);
    while(!Queue.empty()){
        nod=Queue.front();
        Queue.pop();
        for(j=0;j<v[nod].size();j++) {
            vecin=v[nod][j];
            if(d[vecin]>d[nod]+1){
                d[vecin]=d[nod]+1;
                Queue.push(vecin);
            if(d[vecin]>maxi)
                maxi=d[vecin];
            }
        }
    }
}

void afisare() {

    ofstream out("darb.out");
    out<<maxi+1<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}