Pagini recente » Borderou de evaluare (job #1332015) | Borderou de evaluare (job #247777) | Borderou de evaluare (job #1184685) | Borderou de evaluare (job #1594865) | Cod sursa (job #2412863)
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
const int NR = 50000 ;
ifstream in ("biconex.in") ;
ofstream out ("biconex.out") ;
vector < int > v [ NR ] ;
vector < pair < int , int > > st ;
int n , m , lvl [ 100005 ] , lowest [ 100005 ] ;
vector < vector < int > > ans ;
void make_cb ( int x , int y ) {
vector < int > c;
int cx , cy ;
do {
cx = st.back().first ;
cy = st.back().second ;
st.pop_back() ;
c.push_back( cx ) , c.push_back( cy ) ;
}while ( !( cx == x && cy == y ) ) ;
ans.push_back( c ) ;
}
void dfs ( int nod , int father ) {
vector < int > :: iterator it ;
lowest [ nod ] = lvl [ nod ] ;
for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it ) {
if ( *it == father ) continue ;
if ( !lvl [ *it ] ) {
lvl [ *it ] = lvl [ nod ] + 1 ;
st.push_back( mp ( nod , *it ) ) ;
dfs( *it , nod ) ;
lowest [ nod ] = min ( lowest [ nod ] , lowest [ *it ] ) ;
if ( lowest [ *it ] >= lvl [ nod ] ) make_cb ( nod , *it ) ;
} else {
lowest [ nod ] = min ( lowest [ nod ] , lvl [ *it ] ) ;
}
}
}
int main() {
int x , y ;
in >> n >> m ;
lvl [ 1 ] = 1 ;
while ( m -- ) {
in >> x >> y ;
v [ x ].push_back ( y ) ;
v [ y ].push_back ( x ) ;
}
dfs( 1 , 0 ) ;
for ( size_t i = 0 ; i < ans.size() ; ++ i , out << '\n' ) {
sort( ans [ i ].begin() , ans[ i ].end() ) ;
ans [ i ].erase( unique( ans [ i ].begin() , ans [ i ].end()) , ans [ i ].end() ) ;
for ( size_t j = 0 ; j < ans [ i ].size() ; ++ j ) out << ans[ i ][ j ] << ' ' ;
}
}