Cod sursa(job #2789735)

Utilizator Dantelogus99Gruia Gabriel Dantelogus99 Data 27 octombrie 2021 21:19:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.78 kb
#include <fstream>
#include <list>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

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); // lowLink[x] = min(lowLink[x], discOrder[y]), cu Y conectat la X
        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;
    }

    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;
        discOrder[nodS] = lowLink[nodS] = idCurent++;
        stack.push(nodS);
        onStack[nodS] = true;

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

        // 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);
        }
    }
};

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

    Graf G(n, m, true);
    G.citireGraf();

    vector<vector<int>> CTC = G.componenteTareConexe();

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

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