Pagini recente » Cod sursa (job #2068503) | Cod sursa (job #111937) | Cod sursa (job #2003466) | Cod sursa (job #1871645) | Cod sursa (job #411279)
Cod sursa(job #411279)
#include <algorithm>
#include <bitset>
using namespace std;
#define MAX_N 100005
#define MAX_S 10005
char s[ MAX_N ];
int N, M;
int cnt_s, nr_comp, r[ MAX_N ], t[ MAX_N ];
bitset <MAX_N> f;
void read( int &val ) {
while( !isdigit( s[ cnt_s ] ) )
if( ++cnt_s == MAX_S ) {
fread( s, 1, MAX_S, stdin );
cnt_s = 0;
}
val = 0;
while( isdigit( s[ cnt_s ] ) ) {
val = val * 10 + s[ cnt_s ] - '0';
if( ++cnt_s == MAX_S ) {
fread( s, 1, MAX_S, stdin );
cnt_s = 0;
}
}
}
void unite( const int &nod_1, const int &nod_2 ) {
if( r[ nod_1 ] < r[ nod_2 ] )
t[ nod_1 ] = nod_2;
else
t[ nod_2 ] = nod_1;
if( r[ nod_1 ] == r[ nod_2 ] )
++r[ nod_1 ];
}
int find( const int &nod ) {
if( nod != t[ nod ] )
t[ nod ] = find( t[ nod ] );
return t[ nod ];
}
int main() {
freopen( "dfs.in", "r", stdin );
freopen( "dfs.out", "w", stdout );
int i, x, y;
cnt_s = MAX_S - 1;
nr_comp = 0;
read( N );
read( M );
for( i = 1; i <= N; ++i )
t[ i ] = i;
while( M-- ) {
read( x );
read( y );
unite( find( x ), find( y ) );
}
for( i = 1; i <= N; ++i )
f[ find( i ) ] = true;
for( i = 1; i <= N; ++i )
if( f[ i ] == true )
++nr_comp;
printf( "%d", nr_comp );
return 0;
}