Cod sursa(job #1128032)

Utilizator superman_01Avramescu Cristian superman_01 Data 27 februarie 2014 14:58:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>

#define NMAX 100005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)>(b)?(b):(a))

using namespace std;

typedef vector < int > ::iterator vii;

ifstream in ( "ctc.in" );
ofstream out ( "ctc.out" );

vector < int > G[NMAX] , GT[NMAX] , Sol[NMAX];
int N , M , Nr_Scc;
stack < int > S;
bool used[NMAX];


void DFP ( int node )
{
	used[node] = true ;
	for ( vii it = G[node].begin() ; it != G[node].end() ; ++it )
		if ( !used[*it] )
			DFP ( *it );
	S.push( node );
}
void DFM ( int node )
{
	used[node]= true;
	for ( vii it = GT[node].begin() ; it != GT[node].end() ; ++it )
		if ( !used[*it] )
			DFM( *it );
	Sol[Nr_Scc].push_back(node);
}

void Kosaraju ( void )
{
	int i , j ;
	for ( i = 1 ; i <= N ; ++i ) 
		if ( !used[i] )
			DFP ( i );
	memset ( used , 0 , sizeof(used));
	do
	{
		int node = S.top() ;S.pop();
		if ( !used[node] )
		++Nr_Scc,DFM(node);
	}while(!S.empty());	
}


int main ( void )
{
	int i , j , x , y; 
	in >> N  >> M ;
	for( i = 1 ; i <= M ; ++i )
		in >> x >> y ,G[x].push_back(y) , GT[y].push_back(x);
	DFP(1);
	Kosaraju();
	out << Nr_Scc << "\n";
	for ( i = 1 ; i <= Nr_Scc ; ++i )
	{
		for ( vii it = Sol[i].begin()  ; it != Sol[i].end() ; ++it )
			out << *it << " ";
		out << "\n";
	}
	in.close();
	out.close();
	return 0;
}