Cod sursa(job #2814242)

Utilizator Pop_MariaPop Maria Pop_Maria Data 7 decembrie 2021 20:27:15
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

class Graf
{
    int numar_noduri;
    vector <int> lista_adiacenta[100];

public:

    void citire();
    void bfs_darb(int, int&, int&);
    void bfs_darb_init();
};

void Graf :: citire()
{
    int capat_stang, capat_drept;

    fin >> numar_noduri;

    for(int i = 0; i <= numar_noduri; i++)
    {
        lista_adiacenta[i].push_back(-1);
    }

    for(int i = 0; i < numar_noduri; i++)
    {
        fin >> capat_stang >> capat_drept;
        lista_adiacenta[capat_stang].push_back(capat_drept);
        lista_adiacenta[capat_drept].push_back(capat_drept);
    }
}

void Graf :: bfs_darb_init()
{
    int distanta, nod1, nod2;

    bfs_darb(1, nod1, distanta);
    bfs_darb(nod1, nod2, distanta);

    fout << distanta;
}

void Graf :: bfs_darb(const int s, int &u, int &d)
{
    int a;
    int vizitat[numar_noduri + 1] = {};
    int dist[numar_noduri + 1] = {};
    queue <int> coada;

    d = 0;
    dist[s] = 1;
    vizitat[s] = 1;
    coada.push(s);

    while(!coada.empty())
    {
        a = coada.front();
        coada.pop();

        for(int i = 1; i < lista_adiacenta[a].size(); i++)
            if(vizitat[lista_adiacenta[a][i]] == 0)
        {
            vizitat[lista_adiacenta[a][i]] = 1;
            coada.push(lista_adiacenta[a][i]);
            dist[lista_adiacenta[a][i]] = dist[a] + 1;
        }
    }

    for(int i = 1; i <= numar_noduri; i++)
        if(d < dist[i])
        {
            d = dist[i];
            u = i;
        }
}

int main()
{
    Graf x;
    x.citire();
    x.bfs_darb_init();

    fin.close();
    fout.close();

    return 0;
}