Pagini recente » Cod sursa (job #35889) | Cod sursa (job #812601) | Cod sursa (job #2465711) | Cod sursa (job #198054) | Cod sursa (job #403388)
Cod sursa(job #403388)
#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;
}