Pagini recente » Cod sursa (job #2099658) | Cod sursa (job #1320380) | Cod sursa (job #167842) | Cod sursa (job #3249045) | Cod sursa (job #2854240)
#include <stdio.h>
#include <vector>
#define NMAXX 100000
using namespace std;
struct nodes {
int subset;
vector <int> edges;
};
nodes graf[NMAXX];
void dfs( int i, int s ) {
graf[i].subset = s;
for ( int neighbour : graf[i].edges ) {
if ( graf[neighbour].subset != s )
dfs( neighbour, s );
}
}
int main()
{
FILE *fin, *fout;
int n, m, i, nrSubset, a, b;
fin = fopen( "dfs.in", "r" );
fout = fopen( "dfs.out", "w" );
fscanf( fin, "%d%d", &n, &m );
for ( i = 0; i < m; i++ ) {
fscanf( fin, "%d%d", &a, &b );
graf[a].edges.push_back( b );
graf[b].edges.push_back( a );
}
nrSubset = 0;
for ( i = 1; i <= n; i++ ) {
if ( graf[i].subset == 0 )
dfs( i, ++nrSubset );
}
fprintf( fout, "%d", nrSubset );
fclose( fin );
fclose( fout );
return 0;
}