Pagini recente » Cod sursa (job #3152684) | Cod sursa (job #221176) | Cod sursa (job #1444944) | Cod sursa (job #1865728) | Cod sursa (job #1550414)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
FILE *in = fopen ( "biconex.in" , "r" ) , *out = fopen ( "biconex.out" , "w" );
const int VMAX = 100005;
int i , j , vSize , eSize , dep [ VMAX ] , low [ VMAX ] , u , v;
vector < int > g [ VMAX ];
vector < vector < int > > cutG;
stack < pair < int , int > > comp;
void read()
{
fscanf ( in , "%d %d\n" , &vSize , &eSize );
for ( i = 0 ; i < eSize ; i ++ )
{
fscanf ( in , "%d %d\n" , &u , &v );
g [ u ] . push_back ( v );
g [ v ] . push_back ( u );
}
}
void cache( int u , int v )
{
vector < int > aux; int tx , ty;
do {
tx = comp . top() . first , ty = comp . top() . second;
comp . pop();
aux . push_back ( tx ) , aux . push_back ( ty );
} while ( tx != u || ty != v );
cutG . push_back ( aux );
}
void dfs ( int curNode , int prevNode , int depth )
{
dep [ curNode ] = low [ curNode ] = depth;
for ( int i = 0 ; i < g [ curNode ] . size() ; i ++ )
{
int newNode = g [ curNode ] [ i ];
if ( newNode == prevNode ) continue;
if ( dep [ newNode ] != 0 ) low [ curNode ] = min ( low [ curNode ] , dep [ newNode ] ); //already explored
else //new one
{
//push it onto the stack
comp . push ( make_pair( curNode , newNode ) );
dfs ( newNode , curNode , depth + 1 );
low [ curNode ] = min ( low [ curNode ] , low [ newNode ] );
if ( low [ newNode ] >= dep [ curNode ] )
cache ( curNode , newNode );
}
}
}
void cutGraph() { dfs ( 1 , 0 , 1 ); } //current node, previous node and the depth of the current node
void print()
{
fprintf ( out , "%d\n" , cutG . size() );
for ( i = 0 ; i < cutG . size() ; i ++ )
{
sort ( cutG [ i ] . begin() , cutG [ i ] . end() );
cutG [ i ] . erase ( unique ( cutG [ i ] . begin() , cutG [ i ] . end() ) , cutG [ i ] . end() );
for ( j = 0 ; j < cutG [ i ] . size() ; j ++ )
fprintf ( out , "%d " , cutG [ i ] [ j ] );
fprintf ( out , "\n" );
}
}
int main()
{
read();
cutGraph();
print();
return 0;
}