Cod sursa(job #1338012)

Utilizator superman_01Avramescu Cristian superman_01 Data 9 februarie 2015 18:47:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <iostream>
#include <stack>
#include <cstring>


#define NMAX 100005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

ifstream in ( "ctc.in" );
ofstream out ( "ctc.out" );

vector < int > G[NMAX] , GT[NMAX] , Sol[NMAX];

int Answer , N , M ;
bool used[NMAX];
stack < int > S ;

void DFP ( int node ){
   used[node] = true ;
  for ( vector < int > ::iterator it = G[node].begin() ;  it != G[node].end() ; ++it )
     if ( !used[*it] )
        DFP(*it);
  S.push(node);
}

void DFM ( int node ){
    Sol[Answer].push_back( node );
    used[node] = true ;
    for ( vector < int > ::iterator it = GT[node].begin() ; it != GT[node].end() ; ++it )
       if ( !used[*it] )
          DFM(*it);
}
void DoKosaraju ( void ){
    int i , j ;
    for ( i = 1 ; i <= N ; ++i )
       if( !used[i] )
          DFP(i);
    memset ( used , false , sizeof(used));
    while( ! S.empty()){
       int node = S.top();
       S.pop();
       if ( !used[node]){
          ++Answer;
          DFM(node);
       }
    }
  return ;
}


int main ( void ){
    int i , j ;
       in >> N >> M ;
    for ( i = 1 ; i <= M ; ++i  ){
        int x , y;
        in >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    DoKosaraju();
    out << Answer << "\n";
    for ( i = 1 ; i <= Answer ; ++i ){
       for ( vector < int > ::iterator it = Sol[i].begin() ; it!= Sol[i].end() ; ++it )
         out << *it << " ";
    out << "\n";
    }
    return 0 ;
}