Cod sursa(job #2790684)

Utilizator Dantelogus99Gruia Gabriel Dantelogus99 Data 29 octombrie 2021 12:45:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 8.06 kb
#include <fstream>
#include <list>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

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

class Graf
{
    int nrNoduri;
    int nrMuchii;
    bool orientat;

    vector<vector<int>> listaAdiacenta;

public:
    Graf(bool o)
    {
        nrNoduri = 0;
        nrMuchii = 0;
        orientat = o;
    }

    Graf(int n, int m, bool o)
    {
        nrNoduri = n;
        nrMuchii = m;
        orientat = o;
    }

    void citireGraf()
    {
        int x, y;
        vector<int> v;

        for (int i = 0; i < nrMuchii; i++)
            listaAdiacenta.push_back(v);

        if (orientat)
        {
            for (int i = 0; i < nrMuchii; i++)
            {
                fin >> x >> y;
                listaAdiacenta[x].push_back(y);
            }
        }
        else
        {
            for (int i = 0; i < nrMuchii; i++)
            {
                fin >> x >> y;
                listaAdiacenta[x].push_back(y);
                listaAdiacenta[y].push_back(x);
            }
        }
    }

    void afisareGraf()
    {
        fout << "Lista de adiacenta asociata grafului <G>:\n\n\n";
        for (int i = 1; i <= nrNoduri; i++)
        {
            if (listaAdiacenta[i].size() > 0)
            {
                fout << i << " : ";
                for (int x : listaAdiacenta[i])
                    fout << x << " ";
                fout << "\n\n";
            }
        }
    }


    vector<vector<int>> componenteConexe()
    {
        vector<vector<int>> listaCC;
        vector<int> componentaConexa;

        vector<bool> vizitat(nrNoduri + 1, false);

        for (int i = 1; i <= nrNoduri; i++)
            if (!vizitat[i])
            {
                DFS(i, componentaConexa, vizitat);
                listaCC.push_back(componentaConexa);
                componentaConexa.clear();
            }

        return listaCC;
    }

    vector<vector<int>> componenteTareConexe()
    {
        vector<vector<int>> listaCTC;

        vector<int> discOrder(nrNoduri + 1, 0); // nodul x este al discOrder[x]-lea nod obtinut din parcurgerea DFS
        vector<int> lowLink(nrNoduri + 1, 0);
        vector<bool> onStack(nrNoduri + 1, false);
        stack<int> stack; // stiva care valideaza apartenenta unui nod la o componenta conexa

        for (int i = 1; i <= nrNoduri; i++)
            if (discOrder[i] == 0)
                TareConexDFS(i, listaCTC, discOrder, lowLink, stack, onStack);

        return listaCTC;
    }

    vector<vector<int>> componenteBiconexe()
    {
        vector<vector<int>> listaCBC;

        vector<int> adancimi(nrNoduri + 1, 0);
        vector<int> lowLink(nrNoduri + 1, 0); // adancimea maxima pe care o poate atinge un nod prin descendenti
        vector<bool> vizitat(nrNoduri + 1, false);
        stack<int> stack;

        BiconexDFS(1, 1, stack, vizitat, adancimi, lowLink, listaCBC);

        return listaCBC;
    }

    void distanteBFS(int nodS)
    {
        vector<bool> vizitat(nrNoduri + 1, false);
        vector<int> distanta(nrNoduri + 1, -1);

        BFS(nodS, vizitat, distanta);

        for (int i = 1; i <= nrNoduri; i++)
            fout << distanta[i] << " ";
    }

private:
    void DFS(int nodS, vector<int>& componentaConexa, vector<bool>& vizitat)
    {
        vizitat[nodS] = true;
        componentaConexa.push_back(nodS);

        for (auto vecin : listaAdiacenta[nodS])
            if (!vizitat[vecin])
                DFS(vecin, componentaConexa, vizitat);
    }

    void BFS(int nodS, vector<bool>& vizitat, vector<int>& distanta)
    {
        queue<int> queue;
        queue.push(nodS);

        vizitat[nodS] = true;
        distanta[nodS] = 0;

        while (!queue.empty())
        {
            int nodCurent = queue.front();
            //fout << nodCurent << " ";
            queue.pop();

            for (auto vecin : listaAdiacenta[nodCurent])
                if (!vizitat[vecin])
                {
                    queue.push(vecin);
                    vizitat[vecin] = true;
                    distanta[vecin] = distanta[nodCurent] + 1;
                }
        }
    }

    void TareConexDFS(int nodS, vector<vector<int>>& listaCTC, vector<int>& discOrder, vector<int>& lowLink, stack<int>& stack, vector<bool>& onStack)
    {
        static int idCurent = 1;
        stack.push(nodS);
        onStack[nodS] = true;
        discOrder[nodS] = lowLink[nodS] = idCurent++;

        for (auto x : listaAdiacenta[nodS])
        {
            if (discOrder[x] == 0) // daca nodul nu a fost explorat, pornim DFS din el, iar la revenirea din recursie, il incadram intr-o componenta conexa;
            {
                TareConexDFS(x, listaCTC, discOrder, lowLink, stack, onStack);
                lowLink[nodS] = min(lowLink[nodS], lowLink[x]);
            }
            else // daca nodul a fost explorat si se afla pe stiva de validare, il incadram intr-o componenta conexa;
                if (onStack[x])
                    lowLink[nodS] = min(lowLink[nodS], discOrder[x]);
        }

        // daca ID - ul nodului corespunde cu lowLink - value - ul sau, inseamna ca nodul este radacina componentei sale conexe,
        if (lowLink[nodS] == discOrder[nodS])  // si putem scoate de pe stiva toate nodurile pana la nodS, deoarece am terminat de explorat componenta respectiva;
        {
            vector<int> componentaConexa;
            int top;

            do
            {
                top = stack.top();
                stack.pop();
                onStack[top] = false;

                componentaConexa.push_back(top);
            } while (nodS != top);

            listaCTC.push_back(componentaConexa);
        }
    }

    void BiconexDFS(int nodS, int adancimeCurenta, stack<int>& stack, vector<bool>& vizitat, vector<int>& adancimi, vector<int>& lowLink, vector<vector<int>>& listaCBC)
    {
        stack.push(nodS); // stiva retine parcurgerea DFS a subarborilor grafului
        vizitat[nodS] = true;
        adancimi[nodS] = lowLink[nodS] = adancimeCurenta; // adancimi[x] = nivelul de adancime al nodului X din arborele DFS;     lowLink[x] = adancimea minima la care se poate intoarce nodul X;

        for (auto x : listaAdiacenta[nodS])
        {
            if (vizitat[x])
                lowLink[nodS] = min(lowLink[nodS], adancimi[x]); // adancimea minima a nodului curent S = min (adancimea sa minima curenta; adancimea vecinilor sai)
            else
            {
                BiconexDFS(x, adancimeCurenta + 1, stack, vizitat, adancimi, lowLink, listaCBC);
                lowLink[nodS] = min(lowLink[nodS], lowLink[x]); // la intoarcerea din recursie, nodurile cu adancimea < adancimea nodului pe care s-a facut recursia
                                                                // isi minimizeaza adancimea minima lowLink cu a succesorilor;
                if (lowLink[x] == adancimi[nodS])
                {                                   // cand ajungem la succesorul radacinii componentei, eliminam nodurile pana la radacina din stiva, formand o componenta biconexa;
                    vector<int> componentaBiconexa;
                    int top;

                    do
                    {
                        top = stack.top();
                        stack.pop();

                        componentaBiconexa.push_back(top);
                    } while (x != top);

                    componentaBiconexa.push_back(nodS);
                    listaCBC.push_back(componentaBiconexa);
                }
            }
        }
    }
};

int main()
{
    int n, m, s;
    fin >> n >> m;

    Graf G(n, m, false);
    //Graf G(false);

    G.citireGraf();
    //G.afisareGraf();

/* ---> COMPONENTE BICONEXE <--- */
    vector<vector<int>> CBC = G.componenteBiconexe();

    fout << CBC.size() << "\n";

    for (int i = 0; i < CBC.size(); i++)
    {
        for (auto x : CBC[i])
            fout << x << " ";
        fout << "\n";
    }
}