Cod sursa(job #281509)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 15 martie 2009 10:26:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <list>
#include <algorithm>
using namespace std;

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

#ifdef __ACASA__
#define MAX 100
#else
#define MAX 100100
#endif

typedef list<int> li;
typedef list< pair<int,int> > lii;
int Low[MAX], S[MAX];
int k, N, M;
li G[MAX];
list<li> Cache;
lii Stack;

void do_cache( int x, int y ) {
	pair<int,int> thePair(x,y), tmpp;
	li tmp;
	while ( 1 ) { 
		bool ok = ( (tmpp=Stack.back()) == thePair ) ;
		tmp.push_back( tmpp.first );
		tmp.push_back( tmpp.second );
		Stack.pop_back();
		if ( ok ) break;
	};

	tmp.sort();
	tmp.unique();
	Cache.push_back( tmp );
}

void DF( int n, int lvl, int t ) {
	Low[n] = lvl;
	S[ ++k ] = n;
	for ( li::iterator i=G[n].begin(); i!=G[n].end(); ++i ) {
		if ( *i==t ) continue;
		if ( Low[*i] == -1 ) { 
			Stack.push_back( make_pair(n,*i) );
			DF( *i, lvl+1, n );
			Low[n] = min(Low[n], Low[*i]);
			if ( Low[*i] >= lvl )
				do_cache(n,*i);
		}
		else
			Low[n] = min(Low[n], Low[*i]);
	}
}

int main() {
	in >> N >> M;
	while ( M-- ) {
		int x,y;
		in >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	memset( Low, 0xff, sizeof(Low) );
	for ( int i=1; i<=N; ++i ) 
		if ( Low[i] == -1 ) 
			DF(i,0,0);

	out << Cache.size() << "\n";
	for ( list<li>::iterator II=Cache.begin(); II!=Cache.end(); ++II ) {
		li tmp = *II;
		for ( li::iterator i=tmp.begin(); i!=tmp.end(); ++i ) 
			out << *i << " " ;
		out << "\n";
	}
	return 0;
}