Cod sursa(job #1785170)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 20 octombrie 2016 22:05:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

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

const int DIM = 1e5 + 5;

int low[DIM], lev[DIM]; vector<int> g[DIM], st;
bitset<DIM> ma, is; vector< vector<int> > scc;

void dfs( int x, int &cnt ) {
    ma[x] = is[x] = 1; st.push_back(x);
    low[x] = lev[x] = ++ cnt;

    for( auto y : g[x] ) {
        if( ma[y] == 0 )
            dfs( y, cnt );

        if( is[y] == 1 )
            low[x] = min( low[x], low[y] );
    }

    if( low[x] == lev[x] ) {
        int y; scc.push_back( vector<int>(0) );

        do {
            y = st.back(); st.pop_back(); is[y] = 0;
            scc[scc.size() - 1].push_back(y);
        } while( y != x );
    }

    return;
}

int main( int argc, const char *argv[] ) {

    int n, m; in >> n >> m;

    for( int i = 1; i <= m; i ++ ) {
        int x, y; in >> x >> y;
        g[x].push_back( y );
    }

    int cnt = 0;
    for( int i = 1; i <= n; i ++ )
        if( !ma[i] ) dfs( i, cnt );

    out << scc.size() << "\n";

    for( auto l : scc ) {
        for( auto x : l )
            out << x << " ";
        out << "\n";
    }

    return 0;
}