Pagini recente » Cod sursa (job #2631662) | Cod sursa (job #1582986) | Cod sursa (job #2335524) | Cod sursa (job #363192) | Cod sursa (job #2532999)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <ctype.h>
using namespace std;
const int NMAX = 1e5;
vector <int> v[NMAX + 1];
bitset<NMAX + 1> vizitat;
void dfs( int nod ) {
vector<int>::iterator it;
vizitat[nod] = 1;
for ( it = v[nod].begin(); it != v[nod].end(); it ++ ) {
if ( !vizitat[*it] ) {
dfs( *it );
}
}
}
FILE *fin, *fout;
int numar() {
char ch;
int nr = 0;
while ( isspace( ch = fgetc( fin ) ) );
do {
nr = nr * 10 + ch - '0';
} while ( isdigit( ch = fgetc( fin ) ) );
return nr;
}
int main() {
fin = fopen( "dfs.in", "r" );
fout = fopen( "dfs.out", "w" );
int n, m, i, nod1, nod2, componente;
n = numar();
m = numar();
for ( i = 0; i < m; i ++ ) {
nod1 = numar();
nod2 = numar();
v[nod1].push_back( nod2 );
v[nod2].push_back( nod1 );
}
componente = 0;
for ( i = 1; i <= n; i ++ ) {
if ( !vizitat[i] ) {
componente ++;
dfs( i );
}
}
fprintf( fout, "%d\n", componente );
return 0;
}