Cod sursa(job #3288427)

Utilizator pacelaaaCiurea Pavel pacelaaa Data 22 martie 2025 11:21:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ( "biconex.in" );
ofstream fout ( "biconex.out" );

#define cin fin
#define cout fout
#define PB push_back
#define FR( a, b ) for( int a = 0; a < (int) b; a ++ )
#define FOR( a, c, b) for( int a = c; a < (int) b; a ++)

typedef pair<int, int> pii;

const int Nmax = 1e5 + 2, INF = 1e9;
int comp_crt = 0;
vector< vector<int> > comp;
vector<int> adj[Nmax];
bool processed[Nmax];
int parinte[Nmax], adancime[Nmax], low[Nmax];
stack<int> st;

void dfs( int nod, int parinte ) {
  if( processed[nod] )
    return;

  processed[nod] = true;
  adancime[nod] = adancime[parinte] + 1;
  low[nod] = adancime[nod];
  st.push( nod );


  FR( i, adj[nod].size() ) {
    int vecin = adj[nod][i];
    if( !processed[vecin] ) {
      dfs( vecin, nod );
      low[nod] = min( low[nod], low[vecin] );

      if( low[vecin] >= adancime[nod] ) {
        comp.PB( {nod} );
        while( st.top() != vecin ){
          comp[comp.size()-1].PB( st.top() );
          st.pop();
        }
        comp[comp.size() - 1].PB( vecin );
        st.pop();
      }
    } else if( vecin != parinte )
      low[nod] = min( low[nod], adancime[vecin] );
  }
}

int main()
{
    int n, m, u, v;

    cin >> n >> m;
    FR( i, m ) {
      cin >> u >> v;
      adj[u].PB( v );
      adj[v].PB( u );
    }


    adancime[0] = -1;
    dfs( 1, 0 );

    cout << comp.size() << '\n';
    FR( i, comp.size() ) {
      //sort( comp[i].begin(), comp[i].end() );
      FR( j, comp[i].size() )
        cout << comp[i][j] << " ";
      cout << '\n';
    }

    return 0;
}