Cod sursa(job #323860)
#include<stdio.h>
#include<vector>
#define NMAX 100002
using namespace std;
vector< int > G[NMAX];
int C[NMAX];
int val;
void df(const int nod)
{
vector< int >::iterator it;
for( it=G[nod].begin(); it!=G[nod].end(); ++it )
if( C[ *it ]!=val )
{
C[*it]=val;df(*it);
}
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int N,M;
scanf("%d%d",&N,&M);
int i,a1,a2;
for(i=1; i<=M; ++i)
{
scanf("%d%d",&a1,&a2);
G[a1].push_back(a2);
G[a2].push_back(a1);
}
int ANS=N;
for(i=1; i<=N; ++i)
C[i]=i;
for(i=1; i<=N; ++i)
if( C[i]==i )
{
val=i;
df(i);
}
else
--ANS;
printf("%d\n",ANS);
return 0;
}