Cod sursa(job #2516034)

Utilizator Rares31100Popa Rares Rares31100 Data 30 decembrie 2019 11:20:00
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb

#include <fstream>
#include <bitset>
#include <queue>
#define Size 100000
#define Nod first
#define Dist second

using namespace std;

ifstream cin("darb.in");
ofstream cout("darb.out");

int n;
int vf[Size*2+1],urm[Size*2+1],last[Size+1],nr;
int start;
bitset <100001> viz;

void adauga(int from,int to)
{
    vf[++nr]=to;
    urm[nr]=last[from];
    last[from]=nr;
}

int bfs(int x)
{
    viz=0;
    viz[x]=1;

    queue < pair<int,int> > coada;
    coada.push({x,0});

    int maxDist=0;

    while(!coada.empty())
    {
        int nod=coada.front().Nod,dist=coada.front().Dist;
        coada.pop();

        for(int k=last[nod];k;k=urm[k])
            if(!viz[ vf[k] ])
            {
                viz[ vf[k] ]=1;
                coada.push({vf[k],dist+1});
            }

        if(coada.empty())
        {
            maxDist=dist;
            start=nod;
        }
    }

    return maxDist;
}

int main()
{
    cin>>n;

    for(int i,j,k=1;k<=n-1;k++)
    {
        cin>>i>>j;

        adauga(i,j);
        adauga(j,i);
    }

    bfs(1);
    cout<<bfs(start)+1;

    return 0;
}