Cod sursa(job #2102174)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 8 ianuarie 2018 15:05:13
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,grad[100001] ;
struct nod
{
    int info;
    nod *next;
}*L[100001];

void adaug(int x , int y )
{
    nod * aux = new nod;
    aux->info = y;
    aux->next=L[x];
    L[x] = aux;
}

void c()
{
    in >>n ;
    int x ,y ;
    while (in >> x >> y)
    {
        adaug(x,y);
        adaug(y,x);
    }
}
queue <int>q;
bool viz[100001];
int firts_bfs()
{
    q.push(1);
    viz[1]=true;
   int ultim = 1 ;
      while ( !q.empty())
      {
          int node = q.front();
          ultim = node;
          q.pop();
          for ( nod * aux= L[node]; aux; aux= aux->next)
            if(!viz[aux->info])
          {
              q.push(aux->info);
              viz[aux->info]= true;
          }
      }
return ultim;
}

void bfs(int k)
{
    for ( int i =1 ; i <= n ; ++i) viz[i] = false;
       viz[k]=true;
       q.push(k);
       grad[k] = 1 ;
       while (!(q.empty()))
       {
           int node= q.front();
               q.pop();
               for ( nod*aux= L[node]; aux ; aux = aux->next)
                if(!viz[aux->info])
               {
                   q.push(aux->info);
                    viz[aux->info] = true;
                    grad[aux->info] = 1 + grad[node];
               }
       }
}

int main()
{
c();
bfs(firts_bfs());
int maxim=-1;
for ( int i =1; i <= n ; ++i )
     maxim=max(maxim,grad[i]);
     out << maxim;
    return 0;
}