Pagini recente » Cod sursa (job #2818718) | Cod sursa (job #2456681) | Cod sursa (job #1500758) | Cod sursa (job #2939887) | Cod sursa (job #550441)
Cod sursa(job #550441)
#include <stack>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 100011
#define pr pair< int, int >
#define mkpr make_pair< int, int >
using namespace std;
int N, _indexDFS, cbLength;
int indexDFS[N_MAX], lowLink[N_MAX];
stack< pr > S;
vector< int > G[N_MAX], CB[N_MAX];
inline int _min( int x, int y ) { return ( x <= y ? x : y ); }
inline void DFS( int x )
{
indexDFS[x]=lowLink[x]=++_indexDFS;
vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
for( ; it < iend; ++it )
if( 0 == indexDFS[*it] )
{
S.push( mkpr( x, *it ) );
DFS( *it );
lowLink[x]=_min( lowLink[x], lowLink[*it] );
if( lowLink[*it] >= indexDFS[x] )
{
pr y, p0=mkpr( x, *it );
vector< bool > was( N+1 );
do
{
y=S.top(); S.pop();
if( false == was[y.first] )
CB[cbLength].push_back(y.first);
if( false == was[y.second] )
CB[cbLength].push_back(y.second);
was[y.first]=was[y.second]=true;
}while( y != p0 );
++cbLength;
}
}
else lowLink[x]=_min( lowLink[x], indexDFS[*it] );
}
int main( void )
{
int M, x, y;
ifstream in( "biconex.in" );
for( in>>N>>M; M; --M )
{
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
for( x=1; x <= N; ++x )
if( 0 == indexDFS[x] )
DFS(x);
ofstream out( "biconex.out" );
out<<cbLength<<'\n';
for( x=0; x < cbLength; ++x )
{
copy( CB[x].begin(), CB[x].end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
}
return EXIT_SUCCESS;
}