Cod sursa(job #1307743)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 2 ianuarie 2015 18:59:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <queue>
#define DIM 100002
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");
vector <int> v[DIM];
int N,diametru_arbore,last;
void BFS(int x){
    vector <int> inQueue(DIM,0),dist(DIM,0);
    queue <int> Q;
    Q.push(x);
    inQueue[x]=true;
    while(!Q.empty()){
        int node=Q.front();
        Q.pop();
        std::vector <int>::iterator it;
        for(it=v[node].begin();it!=v[node].end();it++){
            if(inQueue[*it]==false){
                Q.push(*it);
                inQueue[*it]=true;
                dist[*it]=dist[node]+1;
                diametru_arbore=dist[*it];
                last=*it;
            }
        }
    }
}
int main(){
    fin>>N;
    for(int i=1;i<N;i++){
        int X,Y;
        fin>>X>>Y;
        v[X].push_back(Y);
        v[Y].push_back(X);
    }
    BFS(1);
    BFS(last);
    fout<<diametru_arbore+1;
}