Pagini recente » Cod sursa (job #2988695) | Cod sursa (job #1407674) | Cod sursa (job #1445297) | Cod sursa (job #2908186) | Cod sursa (job #2354194)
#include <bits/stdc++.h>
using namespace std;
ifstream in ( "biconex.in" ) ;
ofstream out ( "biconex.out" ) ;
const int NR = 100005 ;
vector < int > v [ NR ] ;
stack < pair < int ,int > > st ;
vector < set < int > > C ;
int n , m , x , y ;
vector < int > l ( NR , -1 ) ;
int low [ NR ] ;
void make_cb ( int const x , int const y )
{
set < int > comp ;
int bx ,by ;
do
{
bx = st.top().first ;
by = st.top().second ;
st.pop() ;
comp.insert ( bx ) ;
comp.insert ( by ) ;
}while ( bx != x || by != y );
C.push_back ( comp ) ;
}
void dfs ( int nod , int father , int lvl )
{
vector < int > :: iterator it ;
low [ nod ] = lvl ;
l [ nod ] = lvl ;
for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; it ++ )
{
if ( *it == father ) continue ;
if ( l [ *it ] == -1 )
{
st.push( { nod , *it } ) ;
dfs ( *it , nod , lvl + 1 ) ;
low [ nod ] = min ( low [ nod ] , low [ *it ] ) ;
if ( low [ *it ] >= l [ nod ] )
make_cb ( nod , *it ) ;
}
else low [ nod ] = min ( low [ nod ] , l [ *it ] ) ;
}
}
int main() {
in >> n >> m ;
while ( m -- )
{
in >> x >> y ;
v [ x ].push_back( y ) ;
v [ y ].push_back( x ) ;
}
dfs ( 1 , 0 , 0 ) ;
out << C.size() << '\n' ;
for ( size_t i = 0 ; i < C.size() ; ++ i , out << '\n' )
for ( set < int > :: iterator it = C [ i ].begin() ; it != C [ i ].end() ; ++ it ) out << *it << ' ' ;
return 0;
}