Cod sursa(job #1116909)

Utilizator denis_tdrdenis tdr denis_tdr Data 22 februarie 2014 21:39:02
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#define NMax 100001
using namespace std;

list<int> v[NMax];
list<int>::iterator it;
int n, a, b, c;
vector<bool> viz;

void bf(int from){
    viz=vector<bool>(n+1, false);
    queue<int> coada;
    coada.push(from);
    int crt;
    do{
        a=crt=coada.front();
        coada.pop();
        //cout<<crt<<" ";
        viz[crt]=true;
        for(it=v[crt].begin(); it!=v[crt].end(); it++)
            if(!viz[*it])
                coada.push(*it);
    }while(!coada.empty());
}
void dfStack(int from){
    viz=vector<bool>(n+1, false);
    stack<int> stiva;
    stiva.push(from);
    int crt;
    do{
        b=crt=stiva.top();
        stiva.pop();
        //cout<<crt<<" ";
        viz[crt]=true;
        for(it=v[crt].begin(); it!=v[crt].end(); it++)
            if(!viz[*it])
                stiva.push(*it);
    }while(!stiva.empty());
}
void dfRecursive(int crt, int step){
    viz[crt]=true;
    b=max(step, b);
    for(list<int>::iterator it2=v[crt].begin(); it2!=v[crt].end(); it2++)
        if(!viz[*it2])
            dfRecursive(*it2, step+1);
}
int main(){
    ifstream f("darb.in");
    f>>n;
    for(int 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;
}