Cod sursa(job #1407340)

Utilizator cautionPopescu Teodor caution Data 29 martie 2015 18:33:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <queue>
#define INF 666013
using namespace std;
long n;
vector<long> *graf;
long *viz;
long bf(long x)
{
    queue<long> Q;
    for(long i=1; i<=n; ++i) viz[i]=INF;
    viz[x]=true;
    Q.push(x);
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(vector<long>::iterator it=graf[x].begin(), ed=graf[x].end(); it!=ed; ++it)
            if(viz[*it]==INF)
            {
                viz[*it]=viz[x]+1;
                Q.push(*it);
            }
    }
    return x;
}
int main()
{
    ifstream in("darb.in");
    ofstream out("darb.out");
    long a, b;
    in>>n;
    graf = new vector<long>[n+1];
    viz = new long[n+1];
    for(long i=1; i<n; ++i)
    {
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    a=bf(a);
    b=bf(a);
    out<<viz[b]<<'\n';
    return 0;
}