Cod sursa(job #3355979)

Utilizator andreidumitrache1709andreidumitrache andreidumitrache1709 Data 28 mai 2026 12:02:47
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;

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( "biconex.in" );
    ofstream cout( "biconex.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++;
    for( i = 1 ; i <= n ; i++ )
      if( !tin[i] )
         dfs( i , 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;
}