Cod sursa(job #3293945)

Utilizator vladburacBurac Vlad vladburac Data 13 aprilie 2025 23:10:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;

#ifndef HOME
  ifstream fin( "biconex.in" );
  ofstream fout( "biconex.out" );
  #define cin fin
  #define cout fout
#endif // HOME

vector<int> edges[NMAX+1];
int t = 0;
int timp[NMAX+1], low[NMAX+1];
bool viz[NMAX+1];
stack<int> stiva;
vector <int> components[NMAX+1];
int nrComp = 0;

void dfs( int node, int par = -1 ) {
  low[node] = timp[node] = t++;
  viz[node] = true;
  stiva.push( node );
  for( auto vec: edges[node] ) {
    if( !viz[vec] ) {
      dfs( vec, node );
      low[node] = min( low[node], low[vec] );
      if( low[vec] >= timp[node] ) {
        while( stiva.top() != vec ) {
          components[nrComp].push_back( stiva.top() );
          stiva.pop();
        }
        components[nrComp].push_back( stiva.top() );
        stiva.pop();
        components[nrComp].push_back( node );
        nrComp++;
      }
    }
    else if( vec != par )
      low[node] = min( low[node], timp[vec] );
  }
}
void solve() {
  int n, m, i, j, x, y;
  cin >> n >> m;
  for( i = 0; i < m; i++ ) {
    cin >> x >> y;
    edges[x].push_back( y );
    edges[y].push_back( x );
  }
  dfs( 1 );
  cout << nrComp << "\n";
  for( i = 0; i < nrComp; i++ ) {
    for( auto x: components[i] )
      cout << x << " ";
    cout << "\n";
  }
}
int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    cout.tie( NULL );
    int t = 1;
    //cin >> t;
    while ( t-- )
      solve();
    return 0;
}