Cod sursa(job #257754)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 13 februarie 2009 22:05:17
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <sstream>
#include <list>
#include <stack>
#include <utility>
using namespace std;

#ifdef __ACASA__
#define MAX 2000
#else
#define MAX 100010
#endif

typedef pair<int,int> pii;

list<int> A[MAX];
stack<pii> S;
bool U[MAX];
int H[MAX];
int N, M, nr;
ostringstream buffer(ostringstream::out);

void DF( int x, int h, int last ) {
	U[x] = true;
	H[x] = h;
	for ( list<int>::iterator i=A[x].begin(); i!=A[x].end(); ++i ) {
		if ( *i == last ) continue;
		bool ok = false;
		if ( U[*i]==false ) {
			ok = true;
			S.push( make_pair(x,*i) );
			DF(*i, h+1,x);
		}
		H[x] = H[*i]<H[x] ? H[*i] : H[x];

		if ( H[*i] >= h && ok ) {
			nr ++;
			buffer << S.top().second;
			while ( S.top().first!=x && !S.empty() ) {
 				buffer << " " << S.top().first;
				S.pop();
			}
			buffer << " " << S.top().first;
			S.pop();
			buffer << "\n";
		} 	
	}
}

int main() {
	// load
	ifstream in("biconex.in");
	in >> N >> M;
	while ( M-- ) {
		int x, y;
		in >> x >> y;
		A[x].push_back(y);
		A[y].push_back(x);
	}
	for ( int i=1; i<=N; ++i ) 
		if ( U[i] == false ) 
			DF(i,1,0);

	ofstream("biconex.out") << -1 << "\n" << buffer.str();
	return 0;
}