Cod sursa(job #549367)

Utilizator BitOneSAlexandru BitOne Data 8 martie 2011 15:23:58
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#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];
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;
	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] )
		{
			S.push(*it);
			DFS( *it );
			lowLink[x]=_min( lowLink[x], lowLink[*it] );
		}
		else lowLink[x]=_min( lowLink[x], indexDFS[*it] );
	}
	if( indexDFS[x] == lowLink[x] )
	{
		int y=x;
		do
		{
			CT[ctLength].push_back(y);
			y=S.top(); S.pop();
		}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] )
		{
			S.push(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;
}