Cod sursa(job #285946)
#include<stdio.h>
#define NM 100001
struct nod{
int x;
nod*next;
};
struct lista{
nod*vf,*sf;
};
lista l[NM+1];
int n,m,viz[NM],s[NM];
nod* u[NM];
void addend(lista &l,int x){
nod *n=new nod;
n->x=x;
n->next=NULL;
if(!l.vf) l.vf=n;
else l.sf->next=n;
l.sf=n;
}
void dfs(int start){
int k,up,x;
k=1;s[k]=start;u[k]=l[start].vf;viz[start]=1;
while(k){
up=0;
while(!up&&u[k]){
x=u[k]->x;
if(!viz[x]) up=1;
u[k]=u[k]->next;
}
if(up){
k++;
s[k]=x;
u[k]=l[x].vf;
viz[x]=1;
}
else k--;
}
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int i,x,y,nrcc=0;
scanf("%d%d",&n,&m);
for(i=0;i<m;++i){
scanf("%d%d",&x,&y);
addend(l[x],y);
addend(l[y],x);
}
for(i=1;i<=n;++i)
if(!viz[i]){
nrcc++;
dfs(i);
}
printf("%d",nrcc);
return 0;
}