Cod sursa(job #1386437)

Utilizator BLz0rDospra Cristian BLz0r Data 12 martie 2015 22:58:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

#define Nmax 100002
#define pb push_back

FILE *f = fopen ( "ctc.in", "r" );
FILE *g = fopen ( "ctc.out", "w" );

vector < int > G[Nmax], sol[Nmax];
stack < int > st;
int idx[Nmax], lowlink[Nmax], index = 1, nrsol;
bool inStack[Nmax];

void Tarjan ( int nod ){
	vector < int > :: iterator it;
	
	idx[nod] = index;
	lowlink[nod] = index;
	index++;
	st.push ( nod );
	inStack[nod] = 1;
	
	for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
		if ( !idx[*it] ){
			Tarjan ( *it );
			lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
		}
		else{
			if ( inStack[*it] ){
				lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
			}
		}
	}
	
	if ( lowlink[nod] == idx[nod] ){
		nrsol++;
		int k;
		do{
			k = st.top();
			sol[nrsol].pb ( k );
			st.pop();
			inStack[k] = 0;
		}while ( k != nod );
	}
	
}

int main(){
	int N, M, x, y;
	vector < int > :: iterator it;
	
	fscanf ( f, "%d%d", &N, &M );

	for ( int i = 1; i <= M; ++i ){
		fscanf ( f, "%d%d", &x, &y );
		G[x].pb ( y );
	}
	
	for ( int i = 1; i <= N; ++i )
		if ( !idx[i] )
			Tarjan ( i );
	
	fprintf ( g, "%d\n", nrsol );
	
	for ( int i = 1; i <= nrsol; ++i ){
		for ( it = sol[i].begin(); it < sol[i].end(); ++it )
			fprintf ( g, "%d ", *it );
		fprintf ( g, "\n" );
	}
	
	return 0;
}