Pagini recente » Cod sursa (job #124705) | Cod sursa (job #683104) | Cod sursa (job #1524060) | Cod sursa (job #3240772) | Cod sursa (job #2187302)
#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;
}