Cod sursa(job #2158666)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 10 martie 2018 15:03:26
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <fstream>
#include <queue>
#include <vector>

#define nmax 100001

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
queue <int > coada;
vector < int > nod[nmax];
int diametru,last,n,m,x,y;
int viz[nmax],contor[nmax];
void bfs(int plecare)
{
    for(int i  = 1 ; i <= n ; i++)
         viz[i]=0;
    for(int i =1 ; i <= n ; i++)
        contor[i]=0;
    coada.push(plecare);
    contor[plecare]=1;
    viz[plecare]=1;
    int i,elem;
    while(!coada.empty())
    {
        elem=coada.front();
        for(int i = 0 ; i < nod[elem].size(); i++)
        {
            if(!viz[nod[elem][i]])
        {
            coada.push(nod[elem][i]);
             contor[nod[elem][i]]=contor[elem]+1;
             viz[nod[elem][i]]=1;
             diametru=contor[nod[elem][i]];
             last=nod[elem][i];
        }
    }
    coada.pop();
  }
}
int main()
{
    fin>>n;
    for(int i =1 ; i <= n; i++)
       {
         fin>>x>>y;
        nod[x].push_back(y);
        nod[y].push_back(x);
       }
        bfs(1);
        bfs(last);
        fout<<diametru;

    return 0;
}