Pagini recente » Cod sursa (job #2260957) | Cod sursa (job #2777692) | Cod sursa (job #1462473) | Cod sursa (job #1004279) | Cod sursa (job #1438401)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
#define Nmax 100002
FILE *f = fopen ( "ctc.in", "r" );
FILE *g = fopen ( "ctc.out", "w" );
vector < int > G[Nmax], CTC[Nmax];
bitset < Nmax > inStack;
stack < int > stiva;
int lowlink[Nmax], idx[Nmax], index = 1, ctc;
void Tarjan ( int nod ){
if ( idx[nod] )
return;
vector < int > :: iterator it;
idx[nod] = lowlink[nod] = index++;
stiva.push ( nod );
inStack[nod] = 1;
for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
if ( !idx[*it] ){
Tarjan ( *it );
lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
}
else{
if ( inStack[*it] )
lowlink[nod] = min ( lowlink[nod], idx[*it] );
}
}
if ( lowlink[nod] == idx[nod] ){
int k;
ctc++;
do{
k = stiva.top();
stiva.pop();
inStack[k] = 0;
CTC[ctc].push_back ( k );
}while ( k != nod );
}
}
int main(){
int N, M, x, y;
vector < int > :: iterator it;
fscanf ( f, "%d%d", &N, &M );
for ( int i = 1; i <= M; ++i ){
fscanf ( f, "%d%d", &x, &y );
G[x].push_back ( y );
}
for ( int i = 1; i <= N; ++i )
if ( !idx[i] )
Tarjan ( i );
fprintf ( g, "%d\n", ctc );
for ( int i = 1; i <= ctc; ++i ){
for ( it = CTC[i].begin(); it < CTC[i].end(); ++it )
fprintf ( g, "%d ",*it );
fprintf ( g, "\n" );
}
return 0;
}