Cod sursa(job #2928469)

Utilizator BVLUBogdan Ivan BVLU Data 22 octombrie 2022 23:07:00
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int n, m;
vector < vector < int > > g, gt, ctc; // g = listele de adiacenta, gt = listele de adiacenta pentru graful compus, ctc = componenetele tare conexe
int viz[100000]; // 0 = nu a fost vizitat niciodata, 1 = vizitat dupa primul dfs, 2 = vizitat si prin dfs-ul de pe graful transpus
stack < int > s;

void citire()
{
    ifstream f( "ctc.in" );
    f >> n >> m;
    g.resize( n + 1 );
    gt.resize( n + 1 );
    for( int i = 0; i < m; ++i )
    {
        int x, y;
        f >> x >> y;
        g[x].push_back( y );
        gt[y].push_back( x );
    }
    f.close();
}

void dfs1( int nod )
{
    viz[nod] = 1;
    for( int i = 0; i < g[nod].size(); ++i )
        if( !viz[ g[nod][i] ] )
            dfs1( g[nod][i] );
    s.push( nod );
}

void dfs2( int nod )
{
    viz[nod] = 2;
    ctc[ ctc.size() - 1 ].push_back( nod ); // tinand cont ca adaugam o ctc noua la fiecare dfs pe graful transpus, vom introduce nodurile in noua ctc (ultima)
    for( int i = 0; i < gt[nod].size(); ++i )
        if( viz[ gt[nod][i] ] != 2 )
            dfs2( gt[nod][i] );
}

int main()
{
    citire();
    for( int i = 1; i <= n; ++i )
        if( !viz[i] )
            dfs1( i );
    while( !s.empty() )
    {
        if( viz[ s.top() ] == 1 )
        {
            vector < int > aux;
            ctc.push_back( aux );
            dfs2( s.top() );
        }
        s.pop();
    }
    ofstream g( "ctc.out" );
    g << ctc.size() << "\n";
    for( int i = 0; i < ctc.size(); ++i )
    {
        for( int j = 0; j < ctc[i].size(); ++j )
            g << ctc[i][j] << " ";
        g << "\n";
    }
    g.close();
    return 0;
}

// Algoritmul lui Kosaraju - Complexitate O( n + m )