Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1010259) | Cod sursa (job #2746987) | Cod sursa (job #403946)
Cod sursa(job #403946)
#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;
bit_vector Art;
vector< pr > v;
vector< vector< int > > G, BC;
void GetBiconexC( pr p )
{
pr x;
++lg;
bit_vector 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;
}