Pagini recente » Borderou de evaluare (job #2115973) | Cod sursa (job #1916631)
#include <fstream>
#include <queue>
#include <vector>
#define Nmax 100010
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int n, m, viz[ Nmax ], st[ Nmax ], comp[ Nmax ], nr, x, y;
vector < int > v[ Nmax ], t[ Nmax ], s[ Nmax ];
void DF( int nod )
{
viz[ nod ] = 1;
for ( int i = 0; i < (int)v[ nod ].size(); ++ i )
if ( not viz[ v[ nod ][ i ] ] )
DF( v[ nod ][ i ] );
st[ ++ st[ 0 ] ] = nod;
}
void DF2 ( int nod )
{
comp[ nod ] = 1;
s[ nr ].push_back( nod );
for ( int i = 0; i < (int)t[ nod ].size(); ++ i )
if ( not comp[ t[ nod ][ i ] ] )
DF2( t[ nod ][ i ] );
}
int main()
{
f >> n >> m;
for ( int i = 1; i <= m; ++ i )
{
f >> x >> y;
v[ x ].push_back( y );
t[ y ].push_back( x );
}
for ( int i = 1; i <= n; ++ i )
if ( not viz[ i ] )
DF( i );
while ( st[ 0 ] )
{
if ( not comp[ st[ st[ 0 ] ] ] )
{
nr ++;
DF2( st[ st[ 0 ] -- ] );
}
else st[ 0 ]--;
}
g << nr << '\n';
for ( int i = 1; i <= nr; ++ i )
{
for ( int j = 0; j < (int)s[ i ].size(); ++ j )
g << s[ i ][ j ] << " ";
g << '\n';
}
return 0;
}