Cod sursa(job #3147236)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 24 august 2023 23:46:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define magic_sauce inline __attribute__((always_inline))

magic_sauce int min( int a, int b ){ return a < b ? a : b; }

const int MAXN = 1e5;
const int MAXM = 2e5;

std::vector<int> adj[MAXN];

// componentele biconexe sunt componente conexe pe muchii
struct Edge{
  int u, v;
} stack[MAXM];
int sp;

int highest[MAXN]; // cat de sus poate sa ajunga un nod din subarborele dfs al lui u
int dep[MAXN];

std::vector<int> comp[MAXN];
int ncomp;

void dumb_biconex( Edge e ){
  do{
    sp--;
    comp[ncomp].push_back( stack[sp].u );
    comp[ncomp].push_back( stack[sp].v );
  }while( stack[sp].u != e.u || stack[sp].v != e.v );

  std::sort( comp[ncomp].begin(), comp[ncomp].end() );

  // eliminam duplicatele
  int i, j = 0;

  for( i = 1 ; i < (int)comp[ncomp].size() ; i++ )
    if( comp[ncomp][i] != comp[ncomp][j] )
      comp[ncomp][++j] = comp[ncomp][i];

  comp[ncomp].erase( comp[ncomp].begin() + j + 1, comp[ncomp].end() );

  ncomp++;
}

void dfs( int u, int p ){
  highest[u] = dep[u];

  for( int v : adj[u] ){
    if( dep[v] < 0 ){ // nevizitat
      dep[v] = 1 + dep[u];
      stack[sp++] = Edge{ u, v };
      dfs( v, u );
      highest[u] = min( highest[u], highest[v] );

      if( highest[v] >= dep[u] )
        dumb_biconex( Edge{ u, v } ); // varsa tot din subarbore
    }else if( v != u && dep[v] < dep[u] ){ // vizitat, mai sus
      highest[u] = min( highest[u], dep[v] );
      stack[sp++] = { u, v };
    }
  }
}

int main(){
  FILE *fin = fopen( "biconex.in", "r" );
  FILE *fout = fopen( "biconex.out", "w" );

  int n, m, i, a, b;

  fscanf( fin, "%d%d", &n, &m );
  for( i = 0 ; i < m ; i++ ){
    fscanf( fin, "%d%d", &a, &b );

    adj[a - 1].push_back( b - 1 );
    adj[b - 1].push_back( a - 1 );
  }

  for( i = 0 ; i < n ; i++ )
    dep[i] = highest[i] = -1;

  dep[0] = 0;
  ncomp = 0;
  dfs( 0, 0 );

  fprintf( fout, "%d\n", ncomp );
  for( i = 0 ; i < ncomp ; i++ ){
    for( int v : comp[i] )
      fprintf( fout, "%d ", v + 1 );
    fputc( '\n', fout );
  }

  fclose( fin );
  fclose( fout );
  return 0;
}