Cod sursa(job #146907)
#include <stdio.h>
#include <vector>
#define NMax 100005
int n, m, cnx, uz[NMax];
std::vector<int> a[NMax];
void citire();
void rez();
void dfs( int x );
int main()
{
citire();
rez();
return 0;
}
void dfs( int x )
{
int i, lg;
uz[x] = 1;
lg = a[x].size();
for (i=0; i<lg; i++)
if ( !uz[a[x][i]] )
dfs( a[x][i] );
}
void rez()
{
int i;
for (i=1; i<=n; i++)
if ( !uz[i] )
{
dfs(i);
cnx++;
}
printf( "%d\n", cnx );
}
void citire()
{
int i, x, y;
freopen( "dfs.in", "rt", stdin );
freopen( "dfs.out", "wt", stdout );
scanf( "%d %d", &n, &m );
for (i=0; i<m; i++)
{
scanf( "%d %d", &x, &y );
a[x].push_back( y );
a[y].push_back( x );
}
}