Cod sursa(job #403950)

Utilizator alexandru92alexandru alexandru92 Data 25 februarie 2010 16:44:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 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, start, nrfii;
stack< pr > S;
vector< bool > Art;
vector< pr > v;
vector< vector< int > > G, BC;
void GetBiconexC( pr p )
{
	pr x;
	++lg;
	/*bit_vector*/ vector< bool > uz( v.size() );
	BC.resize( lg );
	do
	{
		x=S.top(); S.pop();
		if( !uz[x.first] )
		{
			uz[x.first]=true;
			BC[lg-1].push_back( x.first+1 );
		}
		if( !uz[x.second] )
		{
			uz[x.second]=true;
			BC[lg-1].push_back( x.second+1 );
		}
	}while( x != p );
	if( !uz[x.first] )
	{
		uz[x.first]=true;
		BC[lg-1].push_back( x.first+1 );
	}
	if( !uz[x.second] )
	{
		uz[x.second]=true;
		BC[lg-1].push_back( x.second+1 );
	}
}
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( *it == x )
			continue;
		if( !v[*it].first )
		{
			if( start == x )
				++nrfii;
			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
			{
				if( start != x )
					Art[x]=true;
				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 );
	Art.resize( N );
	for( M=0; M < N; ++M )
		if( !v[M].first )
		{
			nrfii=0; start=M;
			DFS( M, -1 );
			if( nrfii > 0 )
				Art[M]=true;
		}
	ofstream out( "biconex.out" ); /*
	out<<"Articulation Points are:\n";
	for( M=0; M < N; ++M )
		if( Art[M] )
			out<<M+1<<' ';
	out<<"\nBiconxed Components\n"*/out<<lg<<'\n';
	for( M=0; M < lg; ++M )
	{
		copy( BC[M].begin(), BC[M].end(), ostream_iterator<int>( out, " " ) );
		out<<'\n';
	}
	return 0;
}