Pagini recente » Diferente pentru problema/vmin intre reviziile 4 si 3 | Cod sursa (job #3355978) | Diferente pentru problema/acces intre reviziile 7 si 6 | Cod sursa (job #3352504) | Cod sursa (job #3355976)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int tin[MAXN + 1] , low[MAXN + 1] , cnt , ln;
vector< int >edges[MAXN + 1];
vector< int >ans[MAXN + 1];
stack< pair< int , int >>s;
void print_bcc( int nod , int x ) {
int u , v;
ln++;
map< int , bool >f;
do {
u = s.top().first , v = s.top().second;
s.pop();
ans[ln].push_back( u );
ans[ln].push_back( v );
} while( u != nod || v != x );
f.clear();
}
void dfs( int nod , int p ) {
int num_children = 0;
bool is_ap = 0;
tin[nod] = low[nod] = ++cnt;
for( auto x : edges[nod] ) {
if( !tin[x] ) {
num_children++;
s.push( { nod , x } );
dfs( x , nod );
low[nod] = min( low[nod] , low[x] );
if( low[x] >= tin[nod] ) {
is_ap = true;
print_bcc( nod , x );
}
} else if( x != p ) {
if( tin[x] < tin[nod] ) {
low[nod] = min( low[nod] , low[x] );
s.push( { nod , x } );
}
}
}
}
int main() {
ifstream cin( "bicon.in" );
ofstream cout( "bicon.out" );
int n , m , i , a , b;
cin >> n >> m;
for( i = 1 ; i <= m ; i++ ) {
cin >> a >> b;
edges[a].push_back( b );
edges[b].push_back( a );
}
cnt++;
dfs( 1 , 0 );
cout << ln << '\n';
for( i = 1 ; i <= ln ; i++ ) {
sort( ans[i].begin() , ans[i].end() );
ans[i].erase( unique( ans[i].begin() , ans[i].end() ) , ans[i].end() );
for( auto x : ans[i] )
cout << x << ' ';
cout << '\n';
}
return 0;
}