Pagini recente » Cod sursa (job #2010806) | Cod sursa (job #1880549) | Cod sursa (job #1544141) | Cod sursa (job #400543) | Cod sursa (job #2854343)
#include <stdio.h>
#include <vector>
#define N 100000
std::vector <int> g[N + 1];
int comp[N + 1];
int n;
void dfs( int node ) {
for ( const int& vecin : g[node] ) {
if ( comp[vecin] == 0 ) {
comp[vecin] = comp[node];
dfs( vecin );
}
}
}
inline void addMuchie( int a, int b ) {
g[a].push_back( b );
g[b].push_back( a );
}
int main() {
FILE *fin, *fout;
int m, a, b;
fin = fopen( "dfs.in", "r" );
fscanf( fin, "%d%d", &n, &m );
for ( int i = 0; i < m; i ++ ) {
fscanf( fin, "%d%d", &a, &b );
addMuchie( a, b );
}
fclose( fin );
int cnt = 0;
for ( int i = 1; i <= n; i ++ ) {
if ( comp[i] == 0 ) {
cnt ++;
comp[i] = cnt;
dfs( i );
}
}
fout = fopen( "dfs.out", "w" );
fprintf( fout, "%d\n", cnt );
fclose( fout );
return 0;
}