Pagini recente » Cod sursa (job #1352689) | Cod sursa (job #277798) | Cod sursa (job #457956) | Cod sursa (job #613968) | Cod sursa (job #1128032)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#define NMAX 100005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)>(b)?(b):(a))
using namespace std;
typedef vector < int > ::iterator vii;
ifstream in ( "ctc.in" );
ofstream out ( "ctc.out" );
vector < int > G[NMAX] , GT[NMAX] , Sol[NMAX];
int N , M , Nr_Scc;
stack < int > S;
bool used[NMAX];
void DFP ( int node )
{
used[node] = true ;
for ( vii it = G[node].begin() ; it != G[node].end() ; ++it )
if ( !used[*it] )
DFP ( *it );
S.push( node );
}
void DFM ( int node )
{
used[node]= true;
for ( vii it = GT[node].begin() ; it != GT[node].end() ; ++it )
if ( !used[*it] )
DFM( *it );
Sol[Nr_Scc].push_back(node);
}
void Kosaraju ( void )
{
int i , j ;
for ( i = 1 ; i <= N ; ++i )
if ( !used[i] )
DFP ( i );
memset ( used , 0 , sizeof(used));
do
{
int node = S.top() ;S.pop();
if ( !used[node] )
++Nr_Scc,DFM(node);
}while(!S.empty());
}
int main ( void )
{
int i , j , x , y;
in >> N >> M ;
for( i = 1 ; i <= M ; ++i )
in >> x >> y ,G[x].push_back(y) , GT[y].push_back(x);
DFP(1);
Kosaraju();
out << Nr_Scc << "\n";
for ( i = 1 ; i <= Nr_Scc ; ++i )
{
for ( vii it = Sol[i].begin() ; it != Sol[i].end() ; ++it )
out << *it << " ";
out << "\n";
}
in.close();
out.close();
return 0;
}