Cod sursa(job #2383873)

Utilizator albucristianAlbu Cristian-Gabriel albucristian Data 19 martie 2019 20:51:20
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define ma 1000001
using namespace std;
vector<int>graf[ma];
queue<int>coada;
int dist[ma],viz[ma],ultim,diametru,nod,i;
void bfs(int plecare)
{
    memset(dist,0,ma);
    memset(viz,0,ma);
    coada.push(plecare);
    dist[plecare]=1;
    viz[plecare]=1;
    while(!coada.empty())
    {
        nod=coada.front();
        for(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=0;i<n-1;i++)
    {
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    bfs(1);
    bfs(ultim);
    out<<diametru;
    return 0;
}