Pagini recente » Cod sursa (job #1068976) | Profil Sasha_12454 | Cod sursa (job #252379) | Cod sursa (job #1874144) | Cod sursa (job #1923325)
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
int idx[100010],mini[100010],instack[100010],i,j,n,m,ans,x,y;
stack< int > st;
vector< int > G[100010],CTC[100010];
void DF( int nod )
{
idx[ nod ] = ++idx[ 0 ];
mini[ nod ] = idx[ nod ];
st.push( nod );
instack[ nod ] = 1;
for( auto it : G[ nod ] )
{
if( !idx[ it ] )
DF( it );
if( instack[ it ] )
mini[ nod ] = min( mini[ nod ] , mini[ it ] );
}
if( mini[ nod ] == idx[ nod ] )
{
++ans;
while( st.top() != nod )
{
CTC[ ans ].push_back( st.top() );
instack[ st.top() ] = 0;
st.pop();
}
CTC[ ans ].push_back( nod );
st.pop();
instack[ nod ] = 0;
}
}
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( !idx[ i ] )
DF( i );
}
fout<<ans<<'\n';
for( i = 1 ; i <= ans ; i++ )
{
for( auto it : CTC[ i ] )
fout<<it<<' ';
fout<<'\n';
}
return 0;
}