Cod sursa(job #1166021)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 3 aprilie 2014 09:57:40
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<vector>
#include<stack>
#include<set>

using namespace std;

#define max_n 100010

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

int n , m , niv , ctc , x , y;
int Niv[max_n] , Low[max_n];
bool Viz[max_n];

vector< int > L[max_n];
set< int > Sol[max_n];
stack< int > S;

void read(){
	f>>n>>m;

	for( int i = 1 ; i <= m ; i++ ){
		f>>x>>y;
		L[x].push_back(y);
	}

}

inline int minim( int a , int b ){
	return a < b ? a : b;
}

void dfs( int nod ){

	Niv[nod] = Low[nod] = (++niv);
	S.push( nod ); Viz[nod] = 1;

	for( unsigned int i = 0 ; i < L[nod].size() ; i++ ){
		if( !Viz[ L[nod][i] ] )
			dfs( L[nod][i] );
		Low[nod] = minim( Low[nod] , Low[L[nod][i]] );
	}

	if( Niv[nod] == Low[nod] ){
		ctc++;
		while( S.top() != nod ){
			Sol[ctc].insert( S.top() );
			S.pop();
		}
		Sol[ctc].insert( S.top() );
		S.pop();
	}

}

void print(){

	g<<ctc<<"\n";

	for( int i = 1 ; i <= ctc ; i++ ){
		for( set<int>::iterator it = Sol[i].begin() ; it != Sol[i].end() ; it++ )
			g<<(*it)<<" ";
		g<<"\n";
	}
}

int main(){

	read();

	for( int i = 1 ; i <= n ; i++ )
		if( !Viz[i] )
			dfs(i);

	print();

	return 0;
}