Lab3 - Pb1

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
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;
    }

    GRAF& operator =(GRAF G)
    {
        G.ListaAdiac.resize(ListaAdiac.size());
        for (int index = 0; index < ListaAdiac.size(); ++index)
            for (int index2 = 0; index2 < ListaAdiac[index].size(); ++index2)
                G.ListaAdiac[index].push_back(G.ListaAdiac[index][index2]);

        return G;
    }

    bool verifSucc(int nod, int deCautat)
    {
        int p = 0, u = ListaAdiac[nod].size() - 1;
        while (p <= u)
        {
            int mij = (p + u) / 2;
            if (ListaAdiac[nod][mij] == deCautat)
                return 1;
            else
                if (ListaAdiac[nod][mij] < deCautat)
                    p = mij + 1;
                else
                    u = mij - 1;
        }
        return 0;
    }

    void formareNeorientat(GRAF& G)
    {
        for (int index = 0; index < ListaAdiac.size(); ++index)
            for (int index2 = 0; index2 < ListaAdiac[index].size(); ++index2)
            {
                int succ = ListaAdiac[index][index2];
                if (!verifSucc(succ, index))
                    G.ListaAdiac[succ].push_back(index);
            }

        for (int index = 0; index < ListaAdiac.size(); ++index)
            sort(G.ListaAdiac[index].begin(), G.ListaAdiac[index].end());
    }

    int neviz(vector<bool> viz)
    {
        for (int index = 0; index < ListaAdiac.size(); ++index)
            if (viz[index] == 0)
                return index;
        return -1;
    }

    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, vector<bool>& viz)
    {
        vector<int> pred, comp;
        queue<int> coada;

        if (dest != -1)
        {
            pred.resize(ListaAdiac.size());
            atr(pred, pred.size(), -1);
        }
        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)
                    {
                        pred[succ] = cap;
                        if (succ == dest)
                            return pred;
                    }
                    else
                        comp.push_back(succ);
                }
            }
        }

        return comp;
    }

    vector<int> determinareCale(int start, int dest)
    {
        vector<int> pred, cale;
        vector<bool> viz;
        pred.resize(ListaAdiac.size());
        viz.resize(ListaAdiac.size());

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

        pred = BFS(start, dest, viz);

        if (!pred.empty())
        {
            int nod = dest;
            cale.push_back(nod);
            while (pred[nod] != -1)
            {
                cale.push_back(pred[nod]);
                nod = pred[nod];
            }
        }
        return cale;
    }

    void afisareCale(int start, int dest, vector<int> cale)
    {
        cout << "Calea este: {";
        for (int index = cale.size() - 1; index > 0; --index)
            if (verifSucc(cale[index], cale[index - 1]))
                cout << "(" << cale[index] << ", " << cale[index - 1] << "), ";
            else
                cout << "(" << cale[index - 1] << ", " << cale[index] << "), ";
        cout << "\b\b} \n\n";
    }

    void drum(int start, int dest)
    {
        vector<int> cale;
        cale.resize(determinareCale(start, dest).size());
        cale = determinareCale(start, dest);
        if (!cale.empty())
        {
            cout << "Exista drum de la " << start << " la " << dest << ". \n";
            afisareCale(start, dest, cale);
        }
        else
            cout << "Nu exista drum de la " << start << " la " << dest << ". \n\n";
    }

    void lant(int start, int dest, GRAF GN)
    {
        vector<int> cale;
        cale.resize(GN.determinareCale(start, dest).size());
        cale = GN.determinareCale(start, dest);

        if (!cale.empty())
        {
            cout << "Exista lant de la " << start << " la " << dest << ". \n";
            afisareCale(start, dest, cale);
        }
        else
            cout << "Nu exista lant de la " << start << " la " << dest << ". \n\n";
    }

    void compConexe()
    {
        vector<bool> viz;
        viz.resize(ListaAdiac.size());
        atr(viz, viz.size(), 0);

        int nrCompConexe = 0, nod = neviz(viz);
        do
        {
            vector<int> comp = BFS(nod, -1, viz);
            sort(comp.begin(), comp.end());

            cout << "Componenta conexa cu numarul " << ++nrCompConexe << " contine varfurile {";
            for (auto vf : comp)
                cout << vf << ", ";
            cout << "\b\b} \n";

            nod = neviz(viz);
        } while (nod != -1);

        cout << "Numar total de componente conexe: " << nrCompConexe << endl;
    }

    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 GO;
    GO.citire("liste.in");

    GRAF GN = GO;
    GN.formareNeorientat(GN);

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

    // a)
    int start, dest;
    cout << "Introduceti nodul de start si cel de destinatie pt a determina un drum (daca exista): ";
    cin >> start >> dest;
    if (start != dest)
        GO.drum(start, dest);
    else
        cout << "Varfurile introduse sunt identice. \n\n";

    // b)
    cout << "Introduceti nodul de start si cel de destinatie pt a determina un lant (daca exista): ";
    cin >> start >> dest;
    if (start != dest)
        GO.lant(start, dest, GN);
    else
        cout << "Varfurile introduse sunt identice. \n\n";

    // c)
    cout << "Componentele conexe: \n";
    GN.compConexe();

    GO.clear();
    GN.clear();

    return 0;
}