Cod sursa(job #1816115)

Utilizator jurjstyleJurj Andrei jurjstyle Data 26 noiembrie 2016 09:50:56
Problema Componente tare conexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <list>


using namespace std ;

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

const int Nmax = 100001 ;

vector <int> G[Nmax] , Gt[Nmax] ;
vector <int> Viz ;
int n , m ;
list <int> s ;
vector <int> Sol[Nmax] ;

void read()
{
    f >> n >> m ;
    for ( int cnt = 1 ; cnt <= m ; ++cnt )
    {
        int x , y ;
        f >> x >> y ;
        G[x].push_back (y) ;
        Gt[y].push_back (x) ;
    }
}
void dfs ( int x )
{
    Viz[x] = 1 ;
    for ( const int & y : G[x] )
    {
        if ( Viz[y] ) continue ;
        dfs (y) ;
    }
    s.push_front(x) ;
}
void dfsGT ( int x )
{
    Viz[x] = 1 ;
    for ( const int & y : Gt[x] )
    {
        if ( Viz[y] ) continue ;
        dfsGT (y) ;
    }
}

int main ()
{
    read () ;
    Viz.resize ( n + 1 );
    for ( int i = 1 ; i <= n ; ++i )
        if ( Viz[i] == 0 )
            dfs (i) ;
    int cnt_comp_conexe = 0 ;
    Viz = vector <int> () ;
    Viz.resize(n + 1) ;
    int current_node = 0 ;
    for ( const int & y : s )
        if ( Viz[y] == 0 )
            {
             ++cnt_comp_conexe ;
             dfsGT (y) ;
             current_node = y ;
             Sol[y].push_back (y) ;
            }
        else
            Sol[current_node].push_back (y) ;
    g << cnt_comp_conexe << '\n' ;
    for ( int i = 1 ; i <= n ; ++i )
    {
        if ( !Sol[i].empty ())
            {
             for ( const int & y : Sol[i] )
                g << y << " " ;
             g << "\n" ;
            }
    }
}