Lab3 - Pb2

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct GRAF
{
    vector<vector<int>> ListaAdiac;
    void citire(string fisier)
    {
        ifstream fin(fisier);
        if (!fin)
        {
            cout << "Eroare. \n";
            return;
        }

        int nrNoduri;
        fin >> nrNoduri;
        ListaAdiac.resize(nrNoduri);

        for (int index = 0; index < nrNoduri; ++index)
        {
            int nrSucc;
            fin >> nrSucc;
            for (int index2 = 0; index2 < nrSucc; ++index2)
            {
                int succ;
                fin >> succ;
                ListaAdiac[index].push_back(succ);
            }
        }

        fin.close();
    }

    void afisareListe()
    {
        for (int index = 0; index < ListaAdiac.size(); ++index)
        {
            cout << "L[" << index << "]: ";
            for (int index2 = 0; index2 < ListaAdiac[index].size(); ++index2)
                cout << ListaAdiac[index][index2] << ' ';
            cout << endl;
        }
        cout << endl;
    }

    template<typename T>
    void atr(vector<T>& vect, int dim, int val)
    {
        for (int index = 0; index < dim; ++index)
            vect[index] = val;
    }

    vector<int> BFS(int start, int dest)
    {
        queue<int> coada;
        vector<bool> viz;
        vector<int> comp, dist;

        viz.resize(ListaAdiac.size());
        atr(viz, viz.size(), 0);

        if (dest != -1)
        {
            dist.resize(ListaAdiac.size());
            atr(dist, dist.size(), INT_MAX);
            dist[start] = 0;
        }
        else
            comp.push_back(start);

        viz[start] = 1;
        coada.push(start);

        while (!coada.empty())
        {
            int cap = coada.front();
            coada.pop();
            for (int index = 0; index < ListaAdiac[cap].size(); index++)
            {
                int succ = ListaAdiac[cap][index];
                if (viz[succ] == 0)
                {
                    viz[succ] = 1;
                    coada.push(succ);

                    if (dest != -1)
                    {
                        dist[succ] = dist[cap] + 1;
                        if (succ == dest)
                            return dist;
                    }
                    else
                        comp.push_back(succ);
                }
            }
        }

        return comp;
    }

    int distanta(int start, int dest)
    {
        vector<int> dist;
        dist = BFS(start, dest);

        if (!dist.empty())
            return dist[dest];

        return -1;
    }

    int excentricitate(int nod)
    {
        int excNod = -1;

        for (int index = 0; index < ListaAdiac.size(); ++index)
            if (nod != index && excNod < distanta(nod, index))
                excNod = distanta(nod, index);

        return excNod;
    }

    void clear()
    {
        for (int index = 0; index < ListaAdiac.size(); ++index)
        {
            ListaAdiac[index].clear();
            ListaAdiac[index].shrink_to_fit();
        }
        ListaAdiac.clear();
        ListaAdiac.shrink_to_fit();
    }
};

int main()
{
    GRAF GN;
    GN.citire("liste.in");

    cout << "Listele de adiacenta ale grafului neorientat: \n";
    GN.afisareListe();

    if (GN.BFS(0, -1).size() == GN.ListaAdiac.size())
    {
        int diametru = INT_MIN, raza = INT_MAX;
        for (int index = 0; index < GN.ListaAdiac.size(); ++index)
        {
            int excNod = GN.excentricitate(index);
            cout << "Excentricitatea nodului " << index << " este: " << excNod << endl;

            if (excNod > diametru)
                diametru = excNod;
            if (excNod < raza)
                raza = excNod;
        }
        if (diametru != INT_MIN && raza != INT_MAX)
            cout << "\nDiametrul este " << diametru << " si raza este " << raza << endl;
        else
            cout << "Nu s-au putut afla diametrul si raza. \n";
    }
    else
        cout << "Graful nu este conex. \n";

    GN.clear();
    return 0;
}