Cod sursa(job #2784301)

Utilizator ionut31Ioan Ionescu ionut31 Data 16 octombrie 2021 11:50:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

int vizitat[100005];
int moment[100005]; //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
int low[100005]; //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
stack<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment
vector<set<int>> tareconexe; //vectorul de componente tare-conexe

int n, m, timp=0; // timp = contor de timp pentru crearea vectorului moment
vector<vector<int>> la;

void dfs(int x) //x = nodul curent
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
    in_stack.insert(x);

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            dfs(z);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];

        }
        else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
        {
            //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
            // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
            // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
            if (low[x] > moment[z])
                low[x] = moment[z];
        }
    }
    if(low[x]==moment[x]) //daca nodul e radacina in componenta curenta(am avut un circuit)
    {
        set<int> componenta;
        int y;
        do{
            y=stiva.top();
            stiva.pop();
            in_stack.erase(y);
            componenta.insert(y);
        }while(y!=x);
        tareconexe.push_back(componenta);
    }
}

int main()
{
    fin>>n>>m;
    la.resize(n+1);
    for(int i=0; i<m; ++i)
    {
        int x ,y;
        fin >> x >> y;
        la[x].push_back(y);
    }

    //daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
    for(int j=1; j<=n; ++j)
        if(vizitat[j]==0)
            dfs(j);

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

    for(int i=0; i<tareconexe.size(); ++i)
    {
        for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
            fout << *it << " ";
        fout << "\n";
    }
}