Pagini recente » Cod sursa (job #2463719) | Cod sursa (job #2673112) | Cod sursa (job #1586015) | Cod sursa (job #945754) | Cod sursa (job #1921030)
#include <fstream>
#include <list>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
list< int > G[ 100010 ] , CTC[ 100010 ];
int idx[100010],mini[100010],i,j,n,m,x,y,st[100010],ans,use[100010];
void tarjan( int nod )
{
int poz;
st[ ++st[ 0 ] ] = nod;
poz = st[ 0 ];
use[ nod ] = 1;
idx[ nod ] = ++idx[ 0 ];
mini[ nod ] = idx[ nod ];
for( auto it : G[ nod ] )
{
if( !use[ it ] )
tarjan( it );
mini[ nod ] = min( mini[ nod ] , mini[ it ] );
}
if( mini[ nod ] == idx[ nod ] )
{
++ans;
for( int i = poz ; i <= st[ 0 ] ; i++ )
CTC[ ans ].push_back( st[ i ] );
st[ 0 ] = poz - 1;
}
}
int main()
{
fin>>n>>m;
for( i = 1 ; i <= m ; i++ )
{
fin>>x>>y;
G[ x ].push_back( y );
}
for( i = 1 ; i <= n ; i++ )
{
if( !use[ i ] )
tarjan( i );
}
fout<<ans<<'\n';
for( i = 1 ; i <= ans ; i++ )
{
for( auto it : CTC[ i ] )
fout<<it<<' ';
fout<<'\n';
}
return 0;
}