Pagini recente » Cod sursa (job #525504) | Cod sursa (job #2546405) | Cod sursa (job #2666042) | Cod sursa (job #968587) | Cod sursa (job #806235)
Cod sursa(job #806235)
#include<cstdio>
#include<algorithm>
#include<iterator>
#include<stack>
#include<vector>
using namespace std ;
#define NMAX 100005
vector <int> list [ NMAX ] , afis ;
stack < int > s;
vector < vector < int > > ctc;
int n , m , x , y , index[NMAX]={ 0 } , lowlink[NMAX] , ind = 1 , in_stiva[NMAX]= { 0 };
void citeste()
{
scanf ( "%d%d", &n , &m) ;
for ( int i = 1 ; i <= m ; ++i )
{
scanf("%d%d", &x ,&y ) ;
list[x].push_back( y ) ;
}
}
inline int min(int a , int b )
{
return a <= b ? a : b ;
}
void scrie(vector< vector < int> > comp_t_con)
{
printf("%d\n", comp_t_con.size( ) );
vector< int > afis;
vector< int > :: iterator it ;
for( int i = 0 ; i < comp_t_con.size() ; ++i )
{
afis=comp_t_con [ i ];
for( it = afis .begin() ; it < afis.end() ; ++it )
printf("%d " ,*it);
printf("\n");
}
}
void tarjan( int v )
{
index[ v ] = ind ;
lowlink [ v ] = ind ;
++ind;
s.push( v ) ;
in_stiva[ v ] = 1;
vector < int > ::const_iterator it ;
for( it = list[ v ].begin() ; it <list[ v ].end() ; ++it )
{
if ( ! index [ *it ] )
{
tarjan( *it );
lowlink [ v ] = min ( lowlink[ v ] , lowlink [ *it ] ) ;
}
else
if ( in_stiva [ *it ] )
{
lowlink [ v ] = min ( lowlink[v] , index[ *it ] ) ;
}
}
if( lowlink [ v ] == index [ v ] )
{
int aux ;
afis.clear( );
do
{
afis.push_back (aux= s.top() );
in_stiva[ aux ] = 0;
s.pop();
}while( v != aux );
ctc.push_back( afis );
}
}
int main( )
{
freopen( "ctc.in" , "r" , stdin ) ;
freopen( "ctc.out" , "w" , stdout ) ;
citeste();
for( int i = 1 ; i <= n ; ++i )
{
if ( !index[ i ] )
tarjan( i );
}
scrie( ctc);
return 0 ;
}