Pagini recente » Cod sursa (job #2322647) | Cod sursa (job #2314356) | Cod sursa (job #2479301) | Cod sursa (job #50917) | Cod sursa (job #549374)
Cod sursa(job #549374)
#include <stack>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 100011
using namespace std;
int ctLength, _indexDFS;
bool was[N_MAX], isInS[N_MAX];
int indexDFS[N_MAX], lowLink[N_MAX];
stack< int > S;
vector< int > G[N_MAX], CT[N_MAX];
inline int _min( int x, int y ) { return ( x <= y ? x : y ); }
inline void DFS( int x )
{
was[x]=true;
isInS[x]=true;
S.push(x);
lowLink[x]=indexDFS[x]=++_indexDFS;
vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
for( ; it < iend; ++it )
{
if( false == was[*it] )
{
isInS[*it]=true;
DFS( *it );
lowLink[x]=_min( lowLink[x], lowLink[*it] );
}
else if( isInS[*it] )
lowLink[x]=_min( lowLink[x], indexDFS[*it] );
}
if( indexDFS[x] == lowLink[x] )
{
int y;
do
{
y=S.top(); S.pop();
isInS[y]=false;
CT[ctLength].push_back(y);
}while( y != x );
++ctLength;
}
}
int main( void )
{
int N, M, x, y;
ifstream in( "ctc.in" );
for( in>>N>>M; M; --M )
{
in>>x>>y;
G[x].push_back(y);
}
for( x=1; x <= N; ++x )
if( false == was[x] )
{
DFS(x);
}
ofstream out( "ctc.out" );
out<<ctLength<<'\n';
for( x=0; x < ctLength; ++x )
{
copy( CT[x].begin(), CT[x].end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
}
return EXIT_SUCCESS;
}