Cod sursa(job #2886610)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 7 aprilie 2022 22:26:15
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
// This program was written on 6.04.2022
// for problem biconex
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#include <vector>

#define MAXN 100000
#define NIL -1

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

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

int lvl[MAXN];// -1 daca nodul nu e pe stiva sau nivelul apelului
int viz[MAXN];

int dsu[MAXN];
int size[MAXN];

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

int find( int u ){
  if( dsu[u] == u )
    return u;
  
  return dsu[u] = find( dsu[u] );
}

void unite( int u, int v ){
  u = find( u );
  v = find( v );
  
  if( u == v )
    return;

  if( size[u] < size[v] ){
    dsu[u] = v;
    size[v] += size[u];
  }else{
    dsu[v] = u;
    size[u] += size[v];
  }
}

int dfs( int root, int parrent ){
  int lvlr = lvl[root], lvlv;
  
  viz[root] = 1;
  
  for( int v : adj[root] ){
    if( !viz[v] ){
      lvl[v] = lvl[root] + 1;
      
      lvlv = dfs( v, root );
      
      if( lvlv <= lvl[root] )
        unite( root, v );
      
      lvlr = min( lvlv, lvlr );
    }else if( lvl[v] != NIL && v != parrent )
      lvlr = min( lvl[v], lvlr );
  }
  
  lvl[root] = NIL;
  
  return lvlr;
}

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch;
  
  while( !isdigit( ch = fgetc( fin ) ) );
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( fin ) ) );
  
  return n;
}

int main(){
  fin  = fopen( "biconex.in",  "r" );
  fout = fopen( "biconex.out", "w" );
  
  int n, m, i, a, b, root;
  
  n = fgetint();
  for( m = fgetint() ; m-- ; ){
    a = fgetint() - 1;
    b = fgetint() - 1;
    
    adj[a].push_back( b );
    adj[b].push_back( a );
  }
  
  lvl[0] = 0;
  
  for( i = 0 ; i < n ; i++ ){
    dsu[i] = i;
    size[i] = 1;
  }
  
  dfs( 0, 0 );
  
  ncomp = 0;
  for( i = 0 ; i < n ; i++ ){
    root = find( i );
    
    if( size[root] > 1 ){
      if( !root2comp[root] )
        root2comp[root] = ++ncomp;

      root = root2comp[root] - 1;
    
      comp[root].push_back( i );
    }
  }
  
  for( i = 0 ; i < n ; i++ ){
    for( int j : adj[i] )
      if( j > i && find( i ) != find( j ) ){
        comp[ncomp].push_back( i );
        comp[ncomp++].push_back( j );
      }
  }
  
  fprintf( fout, "%d\n", ncomp );
  for( i = 0 ; i < ncomp ; i++ ){
    for( int j : comp[i] )
      fprintf( fout, "%d ", j + 1 );
      
    fputc( '\n', fout );
  }
  
  fclose( fin );
  fclose( fout );
  return 0;
}