Cod sursa(job #403813)

Utilizator alexandru92alexandru alexandru92 Data 25 februarie 2010 12:50:32
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <stack>
#include <vector>
#include <fstream>
#include <iterator>

/*
 *
 */
using namespace std;
struct pr
{
	int first, second;
	pr() { first=second=0; }
	pr( int a, int b )
	{
		first=a;
		second=b;
	}
	inline bool operator!=( const pr& x )
	{
		return ( x.first != first || x.second != second );
	}
};
int lg, idx;
stack< pr > S;
vector< pr > v;
vector< vector< int > > G;
vector< vector< pr > > BC;
void GetBiconexC( pr p )
{
	pr x;
	++lg;
	BC.resize( lg );
	do
	{
		x=S.top(); S.pop();
		BC[lg-1].push_back( x );
	}while( x != p );
	BC[lg-1].push_back(p);
}
inline const int& min( const int& x, const int& y )
{
	if( x < y )
		return x;
	return y;
}
inline void DFS( int x, int f )
{
	vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
	++idx;
	v[x]=pr( idx, idx );
	for( ; it < iend; ++it )
	{
		if( !v[*it].first )
		{
			S.push( pr( x, *it ) );
			DFS( *it, x );
			v[x].second=min( v[x].second, v[*it].second );
			if( v[*it].second >= v[x].first ) // x - punct de articulatie
				GetBiconexC( pr( x, *it ) );
		}
		else v[x].second=min( v[x].second, v[*it].first );
	}
}
inline ostream& operator<<( ostream& out, const pr& x )
{
	out<<(x.first+1)<<' '<<(x.second+1)<<' ';
	return out;
}
int main( void )
{
	int N, M, x, y;
	ifstream in( "biconex.in" );
	in>>N>>M;
	G.resize(M);
	for( ; M; --M )
	{
		in>>x>>y;
		x-=1; y-=1;
		G[x].push_back( y );
		G[y].push_back( x );
	}
	v.resize( N );
	for( M=0; M < N; ++M )
		if( !v[M].first )
			DFS( M, -1 );
	ofstream out( "biconex.out" );
	out<<lg<<'\n';
	for( M=0; M < N; ++M )
	{
		copy( BC[M].begin(), BC[M].end(), ostream_iterator<pr>( out ) );
		out<<'\n';
	}
	return 0;
}