Pagini recente » Cod sursa (job #2918226) | Cod sursa (job #2501938) | Cod sursa (job #2650432) | Cod sursa (job #177807) | Cod sursa (job #2928591)
#include <stdio.h>
#include <vector>
#define N 100000
std::vector <std::vector<int>> g, revg, ans;
bool parc[N], vizitat[N];
char marked[N];
int n;
void init() {
for ( int i = 0; i < n; i ++ )
parc[i] = false;
}
void dfs( std::vector <std::vector<int>> g, int node ) {
parc[node] = true;
marked[node] ++;
for ( int i = 0; i < g[node].size(); i ++ )
if ( !parc[g[node][i]] )
dfs( g, g[node][i] );
}
void conex( int node ) {
init();
dfs( g, node );
init();
dfs( revg, node );
std::vector <int> aux;
for ( int i = 0; i < n; i ++ ) {
if ( marked[i] == 2 ) {
vizitat[i] = true;
aux.push_back( i );
}
marked[i] = 0;
}
ans.push_back( aux );
}
int main() {
FILE *fin, *fout;
int m, x, y;
fin = fopen( "ctc.in", "r" );
fscanf( fin, "%d%d", &n, &m );
g.resize( n );
revg.resize( n );
for ( int i = 0; i < m; i ++ ) {
fscanf( fin, "%d%d", &x, &y );
x --;
y --;
g[x].push_back( y );
revg[y].push_back( x );
}
fclose( fin );
for ( int i = 0; i < n; i ++ )
if ( !vizitat[i] )
conex( i );
fout = fopen( "ctc.out", "w" );
fprintf( fout, "%d\n", ans.size() );
for ( int i = 0; i < ans.size(); i ++ ) {
for ( int j = 0; j < ans[i].size(); j ++ )
fprintf( fout, "%d ", ans[i][j] + 1 );
fprintf( fout, "\n" );
}
fclose( fout );
return 0;
}