Cod sursa(job #2338928)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 8 februarie 2019 00:05:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std ;
const int NR = 100005 ;
ifstream in ("ctc.in") ;
ofstream out ("ctc.out") ;
vector < int > v_t [ NR ] , ctc [ NR ] , st , v [ NR ] ;
int viz [ NR ] , nrctc  , n , m ;
void dfs ( int nod )
{
    viz [ nod ] = 1 ;
    for ( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
    {
        int vecin = v [ nod ][ i ] ;
        if ( !viz [ vecin ] )   dfs ( vecin ) ;
    }
    st.pb( nod ) ;
}
void dfs_t ( int nod )
{
    viz [ nod ] = 2 ;
    for ( size_t i = 0 ; i < v_t [ nod ].size() ; ++ i )
    {
        int vecin = v_t [ nod ][ i ] ;
        if ( viz [ vecin ] != 2 ) dfs_t ( vecin ) ;
    }
    ctc [ nrctc ].pb ( nod ) ;
}
void solve ( )
{
    for ( int i = 1 ; i <= n ; ++ i )   if ( !viz [ i ] )   dfs ( i ) ;

    while ( st.size() )
        {
            int nod = st.back() ;
            if ( viz [ nod ] != 2 )     dfs_t ( nod ) , ++ nrctc ;
            st.pop_back() ;
        }
    out << nrctc << "\n" ;
    for ( int i = 0 ; i < nrctc ; ++ i , out << '\n' )
    for ( size_t j = 0 ; j < ctc [ i ].size() ; ++ j )
    out << ctc [ i ][ j ] << " " ;

}
int  main ()
{
in >> n >> m ;
while ( m -- )
{
    int x , y ; in >> x >> y ;
    v [ x ].pb( y ) ;
    v_t [ y ].pb ( x ) ;
}
solve() ;
}