Pagini recente » Cod sursa (job #2651597) | Cod sursa (job #3296228) | Cod sursa (job #1259256) | Cod sursa (job #607238) | Cod sursa (job #3297368)
#include <stdio.h>
#include <vector>
#include <algorithm>
const int MAXN = 1e5;
std::vector<int> fwd[MAXN];
std::vector<int> back[MAXN];
bool viz[MAXN];
int ctc[MAXN];
std::vector<int> topo;
void dfs( int u ) {
viz[u] = true;
for( int v : fwd[u] )
if( !viz[v] )
dfs( v );
topo.push_back( u );
}
void paint( int u, int C ) {
ctc[u] = C;
for( int v : back[u] )
if( ctc[v] == -1 )
paint( v, C );
}
int main() {
FILE *fin = fopen( "ctc.in", "r" );
FILE *fout = fopen( "ctc.out", "w" );
int n, m;
fscanf( fin, "%d%d", &n, &m );
for( int i = 0; i < m; i++ ){
int a, b;
fscanf( fin, "%d%d", &a, &b );
a--; b--;
fwd[a].push_back( b );
back[b].push_back( a );
}
for( int i = 0; i < n; i++ )
if( !viz[i] )
dfs( i );
std::reverse( topo.begin(), topo.end() );
for( int i = 0; i < n; i++ )
ctc[i] = -1;
int nctc = 0;
for( int u : topo )
if( ctc[u] == -1 )
paint( u, nctc++ );
std::vector<std::vector<int>> comps(nctc);
for( int i = 0; i < n; i++ )
comps[ctc[i]].push_back( i );
fprintf( fout, "%d\n", (int)comps.size() );
for( auto &comp : comps ){
for( int x : comp )
fprintf( fout, "%d ", x + 1 );
fputc( '\n', fout );
}
fclose( fin );
fclose( fout );
return 0;
}