Pagini recente » Cod sursa (job #2814880) | Cod sursa (job #1281837) | Cod sursa (job #153558) | Istoria paginii runda/tiberiu_popoviciu_pregatire/clasament | Cod sursa (job #1923364)
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
/*
stack< pair<int,int> > st;
vector< int > G[ 100010 ] , sol[100010];*/
int idx[100010],mini[100010],ans,a,b,x,y,n,m,i,instack[100010];
stack< int > st;
vector< int > G[ 100010 ],CTC[100010];
void DF( int nod )
{
mini[ nod ] = idx[ nod ] = ++idx[ 0 ];
instack[ nod ] = 1;
st.push( nod );
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( st.top() );
instack[ nod ] = 0;
st.pop();
}
}
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;
}