Pagini recente » Cod sursa (job #2360671) | Cod sursa (job #2662739) | Cod sursa (job #291062) | Cod sursa (job #2070267) | Cod sursa (job #645006)
Cod sursa(job #645006)
# include <fstream>
# include <vector>
# define dim 100002
# define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
int viz[ dim ], ord[ dim ];
int cr = 0, nr = 0 ;
vector < int > a[ dim ], at[ dim ], d[ dim ];
void dfs( int x )
{
int i;
viz[ x ] = 1;
for ( i = 0 ; i < a[ x ].size() ; i++ )
if ( viz[ a[ x ][ i ] ] == 0 )
dfs( a[ x ][ i ] );
cr++;
ord[ cr ] = x;
}
void dfst( int x )
{
int i;
viz[ x ] = 0 ;
d[ nr ].pb( x );
for ( i = 0 ; i < at[ x ].size() ; i++ )
if ( viz[ at[ x ][ i ] ] )
dfst( at[ x ][ i ] );
}
void citire()
{
int i, x, y;
f >> n >> m;
for ( i = 1 ; i <= m ; i++ )
{
f >> x >> y;
a[ x ].pb( y );
at[ y ].pb( x );
}
}
void afiseaza()
{
int i, j;
/*
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 0 ; j < a[ i ].size() ; j++ )
g << a[ i ][ j ] << " ";
g << "\n";
}*/
// g << "\n";
for ( i = 1 ; i <= n ; i++ )
g << ord[ i ] << " ";
g << "\n";
}
void rezolva()
{
int i;
for ( i = 1 ; i <= n ; i++ )
if ( viz[ i ] == 0 )
dfs( i );
//afiseaza();
for ( i = n ; i >= 1 ; i-- )
if ( viz[ ord [ i ] ] )
{
++nr;
dfst( ord[ i ] );
}
}
void afisare()
{
int i, j;
g << nr << "\n";
for ( i = 1 ; i <= nr; i++ )
{
for ( j = 0 ; j < d[ i ].size() ; j++ )
g << d[ i ][ j ] << " ";
g << "\n";
}
}
int main()
{
citire();
rezolva();
afisare();
return 0;
}