Cod sursa(job #2822154)

Utilizator catarau.bianca.Bianca Catarau catarau.bianca. Data 23 decembrie 2021 17:26:44
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

bool vizitat[100005], vizitat_transpusa[100005];

class graf{
private:
    int n, m;
    vector<int> graf_normal[100005];
    stack<int> S;
    vector<int> graf_transpus[100005];
    vector<int> componente_conexe[100005];
public:
    graf(int n, int m);
    void Citire_cu_transpusa();
    void dfs_kosaraju(int nod);
    void dfs_transpus(int nod, int ct);
    void scc();
    void Graf_Transpus();
    void Parcurgere();
};

graf :: graf(int n, int m)
{
    this->n = n;
    this->m = m;

}

void graf :: Citire_cu_transpusa()
{
    for ( int i = 1; i <= m; i++ )
    {   int x, y;
        f >> x >> y;
        graf_normal[x].push_back(y);
        graf_transpus[y].push_back(x);}
}


void graf :: dfs_kosaraju(int nod)
{
    vizitat[nod] = 1;
    for ( auto i : graf_normal[nod] )
        if ( !vizitat[i] )
            dfs_kosaraju(i);
    S.push(nod);
}





void graf :: scc()
{
    int scc_nr = 0;
    while(!S.empty())
    {   int curent=S.top();
        S.pop();
        if(!vizitat_transpusa[curent])
        {scc_nr ++;
        dfs_transpus(curent, scc_nr);}
    }

    g<<scc_nr<<endl;
    for (int i=1; i<= scc_nr; i++)
    {   for(int j: componente_conexe[i])
                g<<j<<" ";
        g<<endl;
    }
}

void graf::dfs_transpus(int nod, int componenta)
{
    vizitat_transpusa[nod]=1;
    componente_conexe[componenta].push_back(nod);
    for (int i: graf_transpus[nod])
        if (!vizitat_transpusa[i])
            dfs_transpus(i, componenta);
}

void componente_tare_conexe(){
    int n ,m ;
    f >>n>>m;
    graf G(n,m);
    G.Citire_cu_transpusa();
     for (int i=1; i<=n; i++)
        if (!vizitat[i])
            G.dfs_kosaraju(i);
    G.scc();
}
int main()
{
    componente_tare_conexe();

    return 0;
}