Cod sursa(job #3213575)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 13 martie 2024 11:54:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <vector>
#include <bitset>

#define MAX 100001
std::vector<int> nod_invers[ MAX + 1 ];
std::vector<int> rez[ MAX + 1 ];
std::vector<int> nod[ MAX + 1 ];
std::vector<int> sortare;
std::bitset<MAX + 1> ok;
int n, k, x, y;

void dfs( int x, std::vector<int> nod[ MAX + 1 ], std::vector<int> &v ) {
  ok[ x ] = 1;
  for( int N : nod[ x ] )
    if( !ok[ N ] )
      dfs( N, nod, v );
  v.push_back( x );
}

int main()
{
    FILE *fin = fopen( "ctc.in", "r" );
    fscanf( fin, "%d %d", &n, &k );

    for( int i = 0; i < k; i++ ) {
      fscanf( fin, "%d %d\n", &x, &y );
      nod[ x ].push_back( y );
      nod_invers[ y ].push_back( x );
    }
    fclose( fin );

    for( int i = 1; i <= n; i++ )
      if( !ok[ i ] )
        dfs( i, nod, sortare );

    ok.reset();

    int no = 0;
    for( int i = (int)sortare.size() - 1; i >= 0; i-- )
      if( !ok[ sortare[ i ] ] )
        dfs( sortare[ i ], nod_invers, rez[ no++ ] );

    FILE *fout = fopen( "ctc.out", "w" );
    fprintf( fout, "%d\n", no );
    for( int i = 0; i < no; i++ ) {
      for( int a : rez[ i ] )
        fprintf( fout, "%d ", a );
      fprintf( fout, "\n" );
    }
    fclose( fout );
    return 0;
}