Cod sursa(job #2954763)

Utilizator vladburacBurac Vlad vladburac Data 15 decembrie 2022 11:44:15
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;

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

int descop[NMAX+1];
int low[NMAX+1];
vector <int> edges[NMAX+1];
bool viz[NMAX+1];
stack <int> stiva;
int t = 0;

vector<int> biconexe[NMAX+1];
int comp = 0;

void print_bcc( int u ) {
  while( stiva.top() != u ) {
    biconexe[comp].push_back( stiva.top() );
    stiva.pop();
  }
  biconexe[comp].push_back( u );
  stiva.pop();
}
void dfs( int node, int parent ) {
  viz[node] = true;
  descop[node] = low[node] = t++;
  stiva.push( node );
  for( auto vec: edges[node] ) {
    if( !viz[vec] ) {
      dfs( vec, node );
      low[node] = min( low[node], low[vec] );
      if( low[vec] >= descop[node] ) {
        print_bcc( vec );
        biconexe[comp].push_back( node );
        comp++;
      }
    }
    else if( vec != parent && descop[vec] < descop[node] ) {
      low[node] = min( low[node], descop[vec] );
    }
  }
}
int main() {
  int n, m, i, a, b;
  fin >> n >> m;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b;
    edges[a].push_back( b );
    edges[b].push_back( a );
  }
  for( i = 1; i <= n; i++ ) {
    if( !viz[i] )
      dfs( i, 0 );
  }
  fout << comp << "\n";
  for( i = 0; i < comp; i++ ) {
    for( auto elem: biconexe[i] )
      fout << elem << " ";
    fout << "\n";
  }
  return 0;
}