Cod sursa(job #2893264)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 25 aprilie 2022 16:43:10
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
// This program was written on 25.04.2022
// for problem ctc
// by Mircea Rebengiuc

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

#include <vector>

#define MAXN 100000
#define NIL -1

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

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

int stack[MAXN];
int sp;

int lvli[MAXN];
int lvlm[MAXN];
int onstack[MAXN];

int lvl;

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

void tarjan( int u ){
  int v;
  
  lvli[u] = lvlm[u] = lvl++;
  
  stack[sp++] = u;
  onstack[u] = 1;
  
  for( int v : adj[u] ){// declaram in alt scope deci e ok
    if( lvli[v] == NIL ){
      tarjan( v );
      lvlm[u] = min( lvlm[u], lvlm[v] );
    }else if( onstack[v] ){
      lvlm[u] = min( lvlm[u], lvli[v] );
    }
  }
  
  if( lvli[u] == lvlm[u] ){// componenta noua
    do{
      v = stack[--sp];
      onstack[v] = 0;
      comp[u].push_back( v );
    }while( v != u );
    
    ncomp++;
  }
}

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( "ctc.in",  "r" );
  fout = fopen( "ctc.out", "w" );
  
  int n, m, i, a, b;
  
  n = fgetint();
  for( m = fgetint() ; m-- ; ){
    a = fgetint() - 1;
    b = fgetint() - 1;
    
    adj[a].push_back( b );
  }
  
  lvl = 0;
  for( i = 0 ; i < n ; i++ ){
    lvli[i] = lvlm[i] = NIL;
    onstack[i] = 0;
  }
  
  for( i = 0 ; i < n ; i++ )
    if( lvli[i] == NIL )
      tarjan( i );
  
  fprintf( fout, "%d\n", ncomp );
  for( i = 0 ; i < n ; i++ )
    if( comp[i].size() ){
      for( int j : comp[i] )
        fprintf( fout, "%d ", j + 1 );
      fputc( '\n', fout );
    }
  
  fclose( fin );
  fclose( fout );
  return 0;
}