Cod sursa(job #1688368)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 13 aprilie 2016 13:59:28
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 100005
using namespace std;
queue <unsigned int> q;
vector <unsigned int> a[nmax];
unsigned int niv[nmax],n;
unsigned int bf1()
{
    niv[1]=1;q.push(1);
    unsigned int x,y,i,p=1;
    while (!q.empty())
    {
        x=q.front();q.pop();
        for (i=0;i<a[x].size();i++)
        {
            y=a[x][i];
            if (!niv[y])
            {
                niv[y]=niv[x]+1;
                if (niv[y]>niv[p]) p=y;
                q.push(y);
            }
        }
    }
    return p;
}
unsigned int bf2()
{
    unsigned int i,y,x,p=0;
    while (!q.empty())
    {
        x=q.front();q.pop();
        for (i=0;i<a[x].size();i++)
        {
            y=a[x][i];
            if (!niv[y])
            {
                niv[y]=niv[x]+1;
                p=max(p,niv[y]);
                q.push(y);
            }
        }
    }
    return p;
}
int main()
{
    ifstream f("darb.in");
    ofstream g("darb.out");
    unsigned int i,x,y,p;
    f>>n;
    for (i=1;i<n;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    p=bf1();
    memset(niv,0,4*(n+1));
    niv[p]=1;q.push(p);
    g<<bf2()<<'\n';
    f.close();
    g.close();
    return 0;
}