Cod sursa(job #403388)

Utilizator alexandru92alexandru alexandru92 Data 24 februarie 2010 21:52:43
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <stack>
#include <vector>
#include <fstream>
#include <iterator>

/*
 *
 */
using namespace std;
struct pr
{
	int first, second;
	pr() { first=second=0; }
	pr( int x, int y )
	{
		first=x;
		second=y;
	}
	inline bool operator !=( const pr& x )
	{
		return ( x.first != first || x.second != second  );
	}
};
int idx=0, lg;
stack< pr > S;
vector< pr > v;
vector< vector< int > > G;
vector< vector< pr > > BC;
inline int min( int& x, int& y )
{
	if( x < y )
		return x;
	return y;
}
void GetBiconexC( int u, int x )
{
	pr p, p2=pr( u, x );
	BC.resize( ++lg );
	do
	{
		p=S.top(); S.pop();
		BC[lg-1].push_back(p);
	}while( p != p2 );
}		
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( f != *it && v[*it].first < v[x].first ) //insert into stack
			S.push( pr( x, *it ) );
		if( !v[*it].first ) //if not yet visited
		{
			DFS( *it, x );
			v[x].second=min( v[x].second, v[*it].second );
			if( v[*it].second >= v[x].first ) //x - articulation point
			   GetBiconexC( 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(N);
	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 < lg; ++M )
	{
		copy( BC[M].begin(), BC[M].end(), ostream_iterator<pr>(out) );
		out<<'\n';
	}
	return 0;
}