Pagini recente » Cod sursa (job #767059) | Cod sursa (job #1094421) | Cod sursa (job #2323537) | Cod sursa (job #2667218) | Cod sursa (job #1757828)
#include <cstdio>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 100005
vector < int > v[ NMAX ];
stack < pair < int , int > > Q;
vector < int > aux;
vector < vector < int> > sol;
int upBound[ NMAX ],
lowBound[ NMAX ];
void biconex( int nod, int tata, int niv ){
int x, y;
upBound[ nod ] = lowBound[ nod ] = niv;
vector < int > :: iterator it;
for( it = v[ nod ].begin(); it != v[ nod ].end(); ++it ){
if( *it == tata ) continue;
if( !lowBound[ *it ] ){
Q.push( { nod, *it } );
biconex( *it, nod, niv + 1 );
lowBound[ nod ] = min( lowBound[ nod ], lowBound[ *it ] );
if( upBound[ nod ] <= lowBound[ *it ] ){
aux.clear();
do{
x = Q.top().first;
y = Q.top().second;
Q.pop();
aux.push_back( x ); aux.push_back( y );
}while( x != nod || y != *it );
sol.push_back( aux );
}
}
else
lowBound[ nod ] = min( lowBound[ nod ], lowBound[ *it ] );
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n, m, i, j, x, y;
scanf("%d%d",&n,&m);
while( m-- ){
scanf("%d%d",&x,&y);
v[ x ].push_back( y );
v[ y ].push_back( x );
}
biconex( 1, 0, 1 );
printf("%d\n",sol.size());
for( i = 0; i < sol.size(); ++i ){
sort( sol[ i ].begin(), sol[ i ].end() );
for( j = 0; j < sol[ i ].size(); ++j )
if( j == 0 || sol[ i ][ j ] != sol[ i ][ j - 1 ] ) printf("%d ",sol[ i ][ j ]);
printf("\n");
}
return 0;
}