Cod sursa(job #2801631)

Utilizator grecu_tudorGrecu Tudor grecu_tudor Data 16 noiembrie 2021 17:53:43
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int MAXN = 100005;

vector<int> G[MAXN];
vector<int> stk;
bool viz[MAXN];
int lev[MAXN];
int bk[MAXN];

vector<int> bi[MAXN];
int ncbi;

void del( int u ) {
  while ( stk.back() != u ) {
    int x = stk.back();
    bi[ncbi].push_back( x );
    stk.pop_back();
  }
  bi[ncbi++].push_back(u);
}

void dfs( int u, int l ) {
  viz[u] = true;
  lev[u] = bk[u] = l;
  stk.push_back( u );
  for ( int i = 0; i < G[u].size(); ++i ) {
    int v = G[u][i];

    if ( !viz[v] ) {
      dfs(v, l + 1);

      bk[u] = min(bk[u], bk[v]);
      if ( bk[v] >= lev[u] ) {
        del(u);
      }
    } else {
      bk[u] = min(bk[u], lev[v]);
    }
  }
}

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

  fin >> n >> m;
  while ( m-- ) {
    fin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 0);
  fout << ncbi << "\n";
  for ( int c = 0; c < ncbi; ++c ) {
    for ( int i = 0; i < bi[c].size(); ++i ) {
      fout << bi[c][i] << " ";
    }
    fout << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}