Pagini recente » Cod sursa (job #2500599) | Cod sursa (job #2083891) | Cod sursa (job #432778) | Cod sursa (job #2882181) | Cod sursa (job #1117946)
#include <stdio.h>
#define N_MAX 100000
#define M_MAX 200000
typedef char bool;
int list[ M_MAX + 1 ], next[ M_MAX + 1 ], beg[ N_MAX + 1 ], end[ N_MAX + 1 ], sp;
bool seen[ N_MAX + 1 ];
void add( int n1, int n2 ) {
list[ ++ sp ] = n2;
if( beg[ n1 ] ) {
next[ end[ n1 ] ] = sp;
end[ n1 ] = sp;
} else {
beg[ n1 ] = end[ n1 ] = sp;
}
}
void DFS( int node ) {
if( !seen[ node ] ) {
seen[ node ] = 1;
int curr = beg[ node ];
while( curr ) {
DFS( list[ curr ] );
curr = next[ curr ];
}
}
}
int main( ) {
FILE * fin, * fout;
fin = fopen( "dfs.in", "r" );
fout = fopen( "dfs.out", "w" );
int N, M;
fscanf( fin, "%d%d", &N, &M );
int i;
for( i = 1; i <= M; i ++ ) {
int n1, n2;
fscanf( fin, "%d%d", &n1, &n2 );
add( n1, n2 );
}
int num = 0;
for( i = 1; i <= N; i ++ ) {
if( !seen[ i ] ) {
num ++;
DFS( i );
}
}
fprintf( fout, "%d\n", num );
fclose( fin );
fclose( fout );
}