Cod sursa(job #2309750)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 29 decembrie 2018 19:00:09
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
const int NR = 100001 ;
ifstream f ("ctc.in") ;
ofstream g ("ctc.out") ;
vector < int > v [ NR ] ;
vector < int > d ( NR , -1 ) ;
vector < int > st ;
vector < bool > viz ( NR , false ) ;
vector < int > ctc [ NR ] ;
int nrctc ;
int dfs ( int nod , int deph )
{
    viz [ nod ] = true ;
    st.pb( nod ) ;
    d [ nod ] = deph ;

    for ( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
    {
        int vecin = v [ nod ][ i ] ;

        if ( d [ vecin ] == -1 )  d [ nod ] = min ( d [ nod ] , dfs ( vecin , deph + 1 ) ) ;
        else
        {
            if ( viz [ vecin ] )    d [ nod ] = min ( d [ nod ]  , d [ vecin ] ) ;
        }
    }
    int nodulet ;
    if ( deph == d [ nod ] )
    {
        nrctc ++ ;
        do
    {
        nodulet = st.back() ;
        st.pop_back() ;
        ctc[ nrctc] .pb ( nodulet ) ;
        viz [ nodulet ] = false ;
    }
    while ( nodulet != nod ) ;
    }
    return d [ nod ] ;
}
int main()
{
    int n , m , i ; f >> n >> m ;
    while ( m -- )  { int a , b ; f >> a >> b ; v [ a ].pb(b) ; }
    for ( i = 1 ; i <= n ; ++ i )
    if ( d [ i ] == -1 )    dfs ( i , 1 ) ;
    g << nrctc << "\n" ;
    for ( i = 1 ; i <= nrctc ; ++ i , g << "\n" )
    for ( size_t j = 0 ; j < ctc [ i ].size() ; ++ j )  g << ctc [ i ][ j ] << " " ;
f.close() ;
g.close() ;
return 0 ;
}