Cod sursa(job #2383782)

Utilizator albucristianAlbu Cristian-Gabriel albucristian Data 19 martie 2019 19:46:17
Problema Diametrul unui arbore Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
using namespace std;
vector<int>graf[100002];
queue<int>coada;
int dist[100002],viz[100002],ultim,diametru,nod;
void bfs(int plecare)
{
    memset(dist,0,100000);
    memset(viz,0,100000);
    coada.push(plecare);
    dist[plecare]=1;
    viz[plecare]=1;
    while(!coada.empty())
    {
        nod=coada.front();
        for(int i=0;i<graf[nod].size();i++)
        {
            if(!viz[graf[nod][i]])
            {
                dist[graf[nod][i]]=dist[nod]+1;
                viz[graf[nod][i]]=1;
                coada.push(graf[nod][i]);
                ultim=graf[nod][i];
                diametru=dist[graf[nod][i]];
            }
        }
        coada.pop();
    }
}
int main()
{
    int n,a,b;
    ifstream in("darb.in");
    ofstream out("darb.out");
    in>>n;
    for(int i=1;i<=n;i++)
    {
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    bfs(1);
    bfs(ultim);
    out<<diametru;
    return 0;
}