Cod sursa(job #2187302)

Utilizator BarbumateiBarbu Matei Barbumatei Data 26 martie 2018 13:12:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 100000
FILE *fin, *fout;
vector <int> G[NMAX], GT[NMAX], afis[NMAX + 1];
int stiva[NMAX], vf, componenta[NMAX], nrc;
bool viz[NMAX];

void dfsp( int nod ) { ///marcam cu + pe graful citit
  int j;
  viz[nod] = true;
  for ( j = 0; j < G[nod].size(); j++ )
    if ( viz[G[nod][j]] == false )
        dfsp( G[nod][j] );
  stiva[vf++] = nod;
}

void dfsm( int nod ) { ///marcam cu - pe graful aciclic
  int j;
  componenta[nod] = nrc;
  afis[nrc].push_back( nod );
  for ( j = 0; j < GT[nod].size(); j++ )
    if ( componenta[GT[nod][j]] == 0 )
      dfsm( GT[nod][j] );
}

int main() {
  int n, m, i, j;
  fin = fopen( "ctc.in", "r" );
  fout = fopen( "ctc.out", "w" );
  fscanf( fin, "%d%d", &n, &m );
  while ( m-- ) {
    fscanf( fin, "%d%d", &i, &j );
    i--; j--;
    G[i].push_back( j );
    GT[j].push_back( i );
  }
  for ( i = 0; i < n; i++ )
    if ( viz[i] == false )
      dfsp( i );
  nrc = 1; ///numarul componentei conexe
  while ( vf > 0 ) {
    i = stiva[vf - 1];
    if ( componenta[i] == 0 ) {
      dfsm( i );
      nrc++;
    }
    vf--;
  }
  fprintf( fout, "%d\n", nrc - 1 );
  for ( i = 1;  i < nrc; i++ ) {
    for ( j = 0; j < afis[i].size(); j++ )
      fprintf( fout, "%d ", afis[i][j] + 1 );
    fprintf( fout, "\n" );
  }
  fclose( fin );
  fclose( fout );
  return 0;
}