Pagini recente » Cod sursa (job #2527752) | Cod sursa (job #1239970) | Cod sursa (job #1855878) | Cod sursa (job #2340533) | Cod sursa (job #1610284)
/**
* Code by Patrick Sava
* "Spiru Haret" National College of Bucharest
**/
# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"
const char IN [ ] = "biconex.in" ;
const char OUT [ ] = "biconex.out" ;
using namespace std ;
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
const int MAX = 2e5 + 14 ;
vector < int > gr [ MAX ] ;
stack < pair < int , int > > st ;
int level [ MAX ] ;
int low [ MAX ] ;
bitset < MAX > viz ;
vector < int > biconex [ MAX ] ;
int cate ;
unordered_map < int , int > H ;
inline void dfs ( int nod , int lvl )
{
viz [ nod ] = 1 ;
level [ nod ] = lvl ;
low [ nod ] = lvl ;
for ( auto x : gr [ nod ] )
{
if ( viz [ x ] == 0 ){
st.push ( mp ( nod , x ) ) ;
dfs ( x , lvl + 1 ) ;
if ( low [ x ] < low [ nod ] ){
low [ nod ] = low [ x ] ;
}
if ( low [ x ] >= level [ nod ] ) {
H.clear ( ) ;
++ cate ;
while ( !st.empty() and !( st.top().first == nod and st.top().second == x ) )
{
if ( H [ st.top().first ] == 0 ) {
biconex [ cate ].pb ( st.top().first ) ;
H [ st.top().first ] = 1 ;
}
if ( H [ st.top().second ] == 0 ) {
biconex [ cate ].pb ( st.top().second ) ;
H [ st.top().second ] = 1 ;
}
st.pop() ;
}
if ( !st.empty() and st.top().first == nod and st.top().second == x ) {
if ( H [ st.top().first ] == 0 ) {
biconex [ cate ].pb ( st.top().first ) ;
H [ st.top().first ] = 1 ;
}
if ( H [ st.top().second ] == 0 ) {
biconex [ cate ].pb ( st.top().second ) ;
H [ st.top().second ] = 1 ;
}
st.pop() ;
}
}
}
else if ( level [ x ] <= level [ nod ] ) {
st.push ( mp ( nod , x ) ) ;
low [ nod ] = min ( low [ nod ] , level [ x ] ) ;
}
}
}
int main ( void )
{
int n , m ;
cin >> n >> m ;
FORN ( i , 1 , m )
{
int x , y ;
cin >> x >> y ;
gr [ x ].pb ( y ) ;
gr [ y ].pb ( x ) ;
}
dfs ( 1 , 1 ) ;
cout << cate << '\n' ;
FORN ( i , 1 , cate )
{
for ( auto x : biconex [ i ] )
cout << x << ' ' ;
cout << '\n' ;
}
return 0;
}