Cod sursa(job #2812926)

Utilizator andreea_07Andreea Georgescu andreea_07 Data 5 decembrie 2021 14:32:48
Problema Diametrul unui arbore Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define nmax  10000
using namespace std;

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

int n,d_distanta[nmax],visited[nmax],ultimul_element,diametru;
vector <int> graf[nmax];
queue <int> coada;


void  bfs(int nod)
{

for(int i = 1; i <=n; i++)
        {
        visited[i] = 0;
        d_distanta[i]=0;
        }

///marcam ca vizitat nodul de plecare
visited[nod] = 1;
d_distanta[nod] = 1;
coada.push(nod);

 while(!coada.empty())
    {
       int s = coada.front();

      ///luam pe rand toate elementele la care se poate ajunge din s si le adaugam in coada
        vector<int>::iterator it;
        for ( it = graf[s].begin(); it != graf[s].end(); ++it)
        {
            if (!visited[*it])
            {
                d_distanta[*it] = d_distanta[s] + 1; ///distanta va fi egala cu distanta tatalui +1
                visited[*it] = 1;
                coada.push(*it);
                diametru=d_distanta[*it];
                ultimul_element=*it;
            }


        }
            coada.pop(); ///eliminam din coada nodul curent
    }

/*for(int i=1;i<=n;i++)
    cout<<d_distanta[i]<<" ";
*/
}


int main()
{int x,y;
fin>>n;
for(int i=1;i<n;i++)
    {fin>>x>>y;
    graf[x].push_back(y);
    graf[y].push_back(x);
    }

bfs(1);
bfs(ultimul_element);
fout<<diametru;
    return 0;
}