Cod sursa(job #1116923)

Utilizator denis_tdrdenis tdr denis_tdr Data 22 februarie 2014 21:46:27
Problema Diametrul unui arbore Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <queue>
#include <vector>
#define NMax 100001
using namespace std;
vector<int> v[NMax];
vector<bool> viz;
vector<int>::iterator it;
int n,a,b,c,i;
void bf(int from){
    viz=vector<bool>(n+1, false);
    queue<int> coada;
    coada.push(from);
    do{a=coada.front();coada.pop();
        viz[a]=true;
        for(i=0; i<v[a].size(); i++)
			if(!viz[v[a][i]])
				coada.push(v[a][i]);
    }while(coada.size());
}
void dfRecursive(int crt, int step){
    viz[crt]=true;
    b=max(step, b);
    for(i=0; i<v[crt].size(); i++)
        if(!viz[v[crt][i]])
            dfRecursive(v[crt][i], step+1);
}
int main(){
    ifstream f("darb.in");
    f>>n;
    for(i=1;i<n;i++)
        f>>a>>b,v[a].push_back(b),v[b].push_back(a);
    bf(1);
    viz=vector<bool>(n+1, false); b=0;
    dfRecursive(a, 0);
    ofstream g("darb.out");
    g<<(b+1)<<"\n";
    return 0;
}