Cod sursa(job #1687818)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 13 aprilie 2016 09:05:28
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define nmax 100005
using namespace std;
int niv[nmax];
vector <int> a[nmax];
queue <int> q;
vector <int> leaf;
int diametru;
void bf()
{
    int i,x,y;bool ok=1;
    while (!q.empty())
    {
        x=q.front();q.pop();ok=1;
        for (i=0;i<a[x].size();i++)
        {
            y=a[x][i];
            if (!niv[y])
            {
                niv[y]=niv[x]+1;
                q.push(y);ok=0;
            }
        }
        if (ok)
        {
            leaf.push_back(x);
            for (i=leaf.size()-2;i>=0;i--)
            {
                diametru=max(diametru,niv[x]+niv[leaf[i]]-1);
            }
        }
    }
}
int main()
{
    ifstream f("darb.in");
    ofstream g("darb.out");
    int i,n,x,y;
    f>>n;
    for (i=1;i<n;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    niv[1]=1;q.push(1);bf();
    g<<diametru<<'\n';
    f.close();
    g.close();
    return 0;
}