Cod sursa(job #1027201)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 12 noiembrie 2013 16:15:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>

using namespace std;

#define max_n 100010

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

int n , m , x , y , k , nr , niv1;

vector<int>L[max_n] , Ctc[max_n];

int stack[max_n] , niv[max_n] , low[max_n];
bool Fr[max_n];

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

void dfs( int nod ){
	
	stack[++k] = nod;
	
	niv[nod] = ++niv1; low[nod] = niv1;
	
	for( unsigned int i = 0 ; i < L[nod].size() ; i++ ){
		if( niv[L[nod][i]] == 0 )
			dfs( L[nod][i] );
		if( low[L[nod][i]] < low[nod] && Fr[L[nod][i]] == 0 )
			low[nod] = low[L[nod][i]]; 
	}
	
	if( niv[nod] == low[nod] ){
		
		nr++;
		
		do{
			x = stack[k--];
			Ctc[nr].push_back(x);
			Fr[x] = 1;
		}while( x != nod );
		
	}
	
}


int main(){
	
	read();
	
	for( int i = 1 ; i <= n ; i++ )
		if( niv[i] == 0 )
			dfs(i);
	
	g<<nr<<"\n";
	
	for( int i = 1 ; i <= nr ; i++ ){
		for( int j = 0 ; j < Ctc[i].size() ; j++ )
			g<<Ctc[i][j]<<" ";
		g<<"\n";
	}
	
	return 0;
}