Cod sursa(job #900275)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 28 februarie 2013 18:50:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<fstream>
#include<vector>


using namespace std;

#define max_n 100100

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

int ctc , n  , nr , m , a , b , nod2 , j , x;

int index[max_n] , down[max_n] , stiva[max_n];

vector<int> L[max_n];
vector<int> V[max_n];

void read(){
	
	f>> n >> m;
	
	for(int i = 1 ; i <= m ; i++){
		f>> a >> b;
		L[a].push_back(b);
	}
	
}

int minim(int a , int b){
	if(a < b)
		return a;
	return b;
}

void dfs(int nod){
	
	index[nod] = down[nod] = (++nr);
	int nod2;
	
	stiva[ ++stiva[ 0 ] ] = nod;
	
	for(int i = 0 ; i < L[nod].size() ; i++){
		
		nod2 = L[nod][i];
		
		if( index[nod2] == 0 )
			dfs(nod2);
		if( index[nod2] > 0 )
			down[nod] = minim( down[nod2] , down[nod] );
	}
	
	if( index[nod] == down[nod] ){
		
		ctc++; 
		int x;
		
		do{
			x = stiva[ stiva[0]-- ];
			index[x] = - index[x];
			V[ctc].push_back( x );
		}while( x != nod );
		
	}
	
}

void solve(){
	
	for(int i = 1 ; i <= n ; i++)
		if(index[i] == 0)
			dfs(i);
	
}

void print(){
	
	g<< ctc << "\n";
	
	for(int i = 1 ; i <= ctc ; i++){
		
		for( j = 0 ; j < V[i].size() ; j++ )
			g<< V[i][j] << " ";
		
		g<< "\n";
	}
	
}

int main(){
	
	read();
	
	solve();
	
	print();
	
	return 0;
}