Pagini recente » Cod sursa (job #780713) | Cod sursa (job #2782474) | Cod sursa (job #2268458) | Cod sursa (job #2153501) | Cod sursa (job #659105)
Cod sursa(job #659105)
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_N = 100002;
const char infile[] = "dfs.in";
const char outfile[] = "dfs.out";
vector < int > G[ MAX_N ];
int use[ MAX_N ];
int N, M, nr_comp;
void read(){
FILE *f;
int x, y;
f = fopen( infile, "rt" );
fscanf( f, "%d %d", &N, &M );
for( ; M; M-- ){
fscanf( f, "%d %d", &x, &y );
G[ x ].push_back(y);
G[ y ].push_back( x );
}
}
void dfs( int node ){
vector < int > :: iterator it;
use[ node ] = 1;
for( it = G[ node ].begin(); it != G[ node ].end(); ++it )
if( !use[ *it ] )
dfs( *it );
}
void write(){
FILE *g;
g = fopen( outfile, "wt" );
fprintf( g, "%d\n", nr_comp );
}
int main(){
read();
for( int i = 1; i <= N; ++i )
if( !use[ i ] )
dfs( i ), nr_comp++;
write();
return 0;
}